Dividing Splittable Goods Evenly and With Limited Fragmentation

Author Peter Damaschke



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.9.pdf
  • Filesize: 421 kB
  • 13 pages

Document Identifiers

Author Details

Peter Damaschke

Cite AsGet 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.
Keywords
  • packing
  • load balancing
  • weighted graph
  • linear-time algorithm
  • parameterized algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. 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.
  2. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  3. 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.
  4. 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.
  5. Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack problems. Springer, 2004. Google Scholar
  6. 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.
  7. Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford Univ. Press, 2006. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail