TY - GEN

T1 - Efficient splitting of necklaces

AU - Alon, Noga

AU - Graur, Andrei

N1 - Publisher Copyright:
© 2021 Noga Alon and Andrei Graur.

PY - 2021/7/1

Y1 - 2021/7/1

N2 - 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 O(m2/3n), 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.

AB - 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 O(m2/3n), 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.

KW - Approximation algorithms

KW - Discrepancy

KW - Necklace halving

KW - Necklace splitting

KW - Online algorithms

UR - http://www.scopus.com/inward/record.url?scp=85115293317&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85115293317&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ICALP.2021.14

DO - 10.4230/LIPIcs.ICALP.2021.14

M3 - Conference contribution

AN - SCOPUS:85115293317

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021

A2 - Bansal, Nikhil

A2 - Merelli, Emanuela

A2 - Worrell, James

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021

Y2 - 12 July 2021 through 16 July 2021

ER -