ALBERT

Description: 〈h3〉Abstract〈/h3〉 〈p〉A splittable good provided in 〈em〉n〈/em〉 pieces shall be divided as evenly as possible among 〈em〉m〈/em〉 agents, where every agent can take shares from at most 〈em〉F〈/em〉 pieces. We call 〈em〉F〈/em〉 the fragmentation and mainly restrict attention to the cases 〈span〉 〈span〉\(F=1\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(F=2\)〈/span〉 〈/span〉. For 〈span〉 〈span〉\(F=1\)〈/span〉 〈/span〉, the max–min and min–max problems are solvable in linear time. The case 〈span〉 〈span〉\(F=2\)〈/span〉 〈/span〉 has neat formulations and structural characterizations in terms of weighted graphs. First we focus on perfectly balanced solutions. While the problem is strongly NP-hard in general, it can be solved in linear time if 〈span〉 〈span〉\(m\ge n-1\)〈/span〉 〈/span〉, and a solution always exists in this case, in contrast to 〈span〉 〈span〉\(F=1\)〈/span〉 〈/span〉. Moreover, the problem is fixed-parameter tractable in the parameter 〈span〉 〈span〉\(2m-n\)〈/span〉 〈/span〉. (Note that this parameter measures the number of agents above the trivial threshold 〈span〉 〈span〉\(m=n/2\)〈/span〉 〈/span〉.) The structural results suggest another related problem where unsplittable items shall be assigned to subsets so as to balance the average sizes (rather than the total sizes) in these subsets. We give an approximation-preserving reduction from our original splitting problem with fragmentation 〈span〉 〈span〉\(F=2\)〈/span〉 〈/span〉 to this averaging problem, and some approximation results in cases when 〈em〉m〈/em〉 is close to either 〈em〉n〈/em〉 or 〈em〉n〈/em〉 / 2.〈/p〉