License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.9
URN: urn:nbn:de:0030-drops-80579
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8057/
Go to the corresponding LIPIcs Volume Portal

Damaschke, Peter

Dividing Splittable Goods Evenly and With Limited Fragmentation

pdf-format:
LIPIcs-MFCS-2017-9.pdf (0.4 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{damaschke:LIPIcs:2017:8057,
  author =	{Peter Damaschke},
  title =	{{Dividing Splittable Goods Evenly and With Limited Fragmentation}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{9:1--9:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8057},
  URN =		{urn:nbn:de:0030-drops-80579},
  doi =		{10.4230/LIPIcs.MFCS.2017.9},
  annote =	{Keywords: packing, load balancing, weighted graph, linear-time algorithm, parameterized algorithm}
}

Keywords: packing, load balancing, weighted graph, linear-time algorithm, parameterized algorithm
Collection: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Issue Date: 2017
Date of publication: 01.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI