Efficient Splitting of Necklaces

Authors Noga Alon, Andrei Graur



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.14.pdf
  • Filesize: 0.66 MB
  • 17 pages

Document Identifiers

Author Details

Noga Alon
  • Department of Mathematics, Princeton University, NJ, USA
  • Schools of Mathematics and Computer Science, Tel Aviv University, Israel
Andrei Graur
  • Department of Management Science and Engineering, Stanford University, CA, USA

Cite AsGet BibTex

Noga Alon and Andrei Graur. Efficient Splitting of Necklaces. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.14

Abstract

We provide efficient approximation algorithms for the Necklace Splitting problem. The input consists of a sequence of beads of n types and an integer k. The objective is to split the necklace, with a small number of cuts made between consecutive beads, and distribute the resulting intervals into k collections so that the discrepancy between the shares of any two collections, according to each type, is at most 1. We also consider an approximate version where each collection should contain at least a (1-ε)/k and at most a (1+ε)/k fraction of the beads of each type. It is known that there is always a solution making at most n(k-1) cuts, and this number of cuts is optimal in general. The proof is topological and provides no efficient procedure for finding these cuts. It is also known that for k = 2, and some fixed positive ε, finding a solution with n cuts is PPAD-hard. We describe an efficient algorithm that produces an ε-approximate solution for k = 2 making n (2+log (1/ε)) cuts. This is an exponential improvement of a (1/ε)^O(n) bound of Bhatt and Leighton from the 80s. We also present an online algorithm for the problem (in its natural online model), in which the number of cuts made to produce discrepancy at most 1 on each type is Õ(m^{2/3} n), where m is the maximum number of beads of any type. Lastly, we establish a lower bound showing that for the online setup this is tight up to logarithmic factors. Similar results are obtained for k > 2.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • necklace splitting
  • necklace halving
  • approximation algorithms
  • online algorithms
  • discrepancy

Metrics

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

References

  1. Noga Alon. Splitting necklaces. Advances in Mathematics, 63(3):247-253, 1987. Google Scholar
  2. Noga Alon. Non-constructive proofs in Combinatorics. Proceedings of the International Congress of Mathematicians (ICM), 63:1421-1429, 1990. Google Scholar
  3. Noga Alon, Michael Krivelevich, Joel H. Spencer, and Tibor Szabó. Discrepancy Games. The Electronic Journal of Combinatorics, 12(1):R51, 2005. Google Scholar
  4. Noga Alon, Dana Moshkovitz, and Muli Safra. Algorithmic construction of sets for k-restrictions. ACM Transactions on Algorithms, 2(2):153-177, 2006. Google Scholar
  5. Noga Alon and Douglas B West. The Borsuk-Ulam Theorem and Bisection of Necklaces. Proceedings of the American Mathematical Society, 98(4):623-628, 1986. Google Scholar
  6. Nikhil Bansal. Constructive Algorithms for Discrepancy Minimization. Proc. 51st Symposium on Foundations of Computer Science (IEEE), pages 3-10, 2010. Google Scholar
  7. Nikhil Bansal and Joel H. Spencer. Deterministic Discrepancy Minimization. Algorithmica, 67(4):451-471, 2013. Google Scholar
  8. Nikhil Bansal and Joel H. Spencer. On-line Balancing of Random Inputs. Random Structures and Algorithms, 57(4):879-891, 2020. Google Scholar
  9. Sandeep N. Bhatt and Frank T. Leighton. A Framework For Solving VLSI Graph Layout Problems. Journal of Computer and System Sciences, 28(2):300-343, 1984. Google Scholar
  10. Sandeep N. Bhatt and Charles E. Leiserson. How to assemble tree machines. Proceedings of the 14th Symposium on the Theory of Computing, San Francisco, pages 99-104, 1981. Google Scholar
  11. Paul Simon Bonsma, Thomas Epping, and Winfried Hochstättler. Complexity results on restricted instances of a paint shop problem for words. Discrete Appl. Math, 154(9):1335-1343, 2006. Google Scholar
  12. Steven J. Brams and Alan D. Taylor. Fair division: From cake-cutting to dispute resolution. Cambridge University Press, 1996. Google Scholar
  13. Bruno Codenotti, Amin Saberi, Kasturi Varadarajan, and Yinyu Ye. The complexity of equilibria: Hardness results for economies via a correspondence with games. Theoretical Computer Science, 408(2-3):188-198, 2008. Google Scholar
  14. Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The Complexity of Computing a Nash Equilibrium. Theoretical Computer Science, 39(1):195-259, 2009. Google Scholar
  15. Aris Filos-Ratsikas, Soren Kristoffer Stiil Frederiksen, Paul W. Goldberg, and Jie Zhang. Hardness Results for Consensus Halving. 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 24:1-24:16, 2018. Google Scholar
  16. Aris Filos-Ratsikas and Paul W. Goldberg. Consensus Halving is PPA-Complete. Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC), pages 51-64, 2018. Google Scholar
  17. Aris Filos-Ratsikas and Paul W. Goldberg. The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches. Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC), pages 638-649, 2019. Google Scholar
  18. Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki, and Manolis Zampetakis. Consensus Halving: Does it Ever Get Easier? Proceedings of the 21st ACM Conference on Economics and Computation, pages 381-399, 2020. Google Scholar
  19. Charles H. Goldberg and Douglas B. West. Bisection of circle colorings. SIAM J. Algebraic Discrete Methods, 6(1):93-106, 1985. Google Scholar
  20. Charles R. Hobby and John R. Rice. A moment problem in L₁ approximation. Proceedings of the American Mathematical Society, 16(4):665-670, 1965. Google Scholar
  21. Frédéric Meunier. Simplotopal maps and necklace splitting. Discrete Mathematics, 323:14-26, 2014. Google Scholar
  22. Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498-532, 1994. Google Scholar
  23. Robert Tijdeman. On a distribution problem in finite and countable sets. Journal of Combinatorial Theory, Series A, 15(2):129-137, 1973. 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