LIPIcs.MFCS.2017.9.pdf
- Filesize: 421 kB
- 13 pages
Document
Dividing Splittable Goods Evenly and With Limited Fragmentation
Author
-
Part of:
Volume:
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-12-01
Cite As Get BibTex
Peter Damaschke. Dividing Splittable Goods Evenly and With Limited Fragmentation. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.MFCS.2017.9
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.
Subject Classification
Keywords
- packing
- load balancing
- weighted graph
- linear-time algorithm
- parameterized algorithm
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, and Robert Endre Tarjan. Time bounds for selection. J. Comput. Syst. Sci., 7(4):448-461, 1973. URL: http://dx.doi.org/10.1016/S0022-0000(73)80033-9.
-
M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
- Dorit S. Hochbaum and David B. Shmoys. A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach. SIAM J. Comput., 17(3):539-551, 1988. URL: http://dx.doi.org/10.1137/0217033.
- Ellis Horowitz and Sartaj Sahni. Exact and approximate algorithms for scheduling nonidentical processors. J. ACM, 23(2):317-327, 1976. URL: http://dx.doi.org/10.1145/321941.321951.
-
Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack problems. Springer, 2004.
- John Martinovic and Guntram Scheithauer. Integer rounding and modified integer rounding for the skiving stock problem. Discrete Optimization, 21:118-130, 2016. URL: http://dx.doi.org/10.1016/j.disopt.2016.06.004.
-
Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford Univ. Press, 2006.