DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2021.14

Efficient Splitting of Necklaces

Authors: Noga Alon and Andrei Graur

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

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 Õ(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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{alon_et_al:LIPIcs.ICALP.2021.14,
  author =	{Alon, Noga and Graur, Andrei},
  title =	{{Efficient Splitting of Necklaces}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.14},
  URN =		{urn:nbn:de:0030-drops-140832},
  doi =		{10.4230/LIPIcs.ICALP.2021.14},
  annote =	{Keywords: necklace splitting, necklace halving, approximation algorithms, online algorithms, discrepancy}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2020.64

New Query Lower Bounds for Submodular Function Minimization

Authors: Andrei Graur, Tristan Pollner, Vidhya Ramaswamy, and S. Matthew Weinberg

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract

We consider submodular function minimization in the oracle model: given black-box access to a submodular set function f:2^[n] → ℝ, find an element of arg min_S {f(S)} using as few queries to f(⋅) as possible. State-of-the-art algorithms succeed with Õ(n²) queries [Yin Tat Lee et al., 2015], yet the best-known lower bound has never been improved beyond n [Nicholas J. A. Harvey, 2008]. We provide a query lower bound of 2n for submodular function minimization, a 3n/2-2 query lower bound for the non-trivial minimizer of a symmetric submodular function, and a binom{n}{2} query lower bound for the non-trivial minimizer of an asymmetric submodular function. Our 3n/2-2 lower bound results from a connection between SFM lower bounds and a novel concept we term the cut dimension of a graph. Interestingly, this yields a 3n/2-2 cut-query lower bound for finding the global mincut in an undirected, weighted graph, but we also prove it cannot yield a lower bound better than n+1 for s-t mincut, even in a directed, weighted graph.

Cite as

Andrei Graur, Tristan Pollner, Vidhya Ramaswamy, and S. Matthew Weinberg. New Query Lower Bounds for Submodular Function Minimization. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{graur_et_al:LIPIcs.ITCS.2020.64,
  author =	{Graur, Andrei and Pollner, Tristan and Ramaswamy, Vidhya and Weinberg, S. Matthew},
  title =	{{New Query Lower Bounds for Submodular Function Minimization}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{64:1--64:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.64},
  URN =		{urn:nbn:de:0030-drops-117493},
  doi =		{10.4230/LIPIcs.ITCS.2020.64},
  annote =	{Keywords: submodular functions, query lower bounds, min cut}
}

Search Results

Documents authored by Graur, Andrei

Efficient Splitting of Necklaces

Abstract

Cite as

New Query Lower Bounds for Submodular Function Minimization

Abstract

Cite as

Thanks for your feedback!

Could not send message