CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Dividing splittable goods evenly and with limited fragmentation

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
42nd International Symposium on Mathematical Foundations of Computer Science MFCS 2017 (2017)
[Konferensbidrag, refereegranskat]

A splittable good provided in n pieces shall be divided as evenly as possible among m agents, where every agent can take shares of at most F pieces. We call F the fragmentation. For F=1 we can solve the max-min and min-max problems in linear time. The case F=2 has neat formulations and structural characterizations in terms of weighted graphs. Here we focus on perfectly balanced solutions. While the problem is strongly NP-hard in general, it can be solved in linear time if m>n-2, and a solution always exists in this case. Moreover, case F=2 is fixed-parameter tractable in the parameter 2m-n. The results also give rise to various open problems.

Nyckelord: packing, load balancing, weighted graph, linear-time algorithm, parameterized algorithm



Denna post skapades 2017-10-05.
CPL Pubid: 252344