2026-07-23T21:02:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8057 2024-03-06T10:40:50Z ddc:004 open_access

Dividing Splittable Goods Evenly and With Limited Fragmentation Damaschke, Peter packing load balancing weighted graph linear-time algorithm parameterized algorithm 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-1, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Peter Damaschke 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.9 urn:nbn:de:0030-drops-80579 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.9 eng https://creativecommons.org/licenses/by/3.0/legalcode