License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.57
URN: urn:nbn:de:0030-drops-175606
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17560/
Go to the corresponding LIPIcs Volume Portal

Goldberg, Paul ; Li, Jiawei

Consensus Division in an Arbitrary Ratio

pdf-format:
LIPIcs-ITCS-2023-57.pdf (0.9 MB)

Abstract

We consider the problem of partitioning a line segment into two subsets, so that n finite measures all have the same ratio of values for the subsets. Letting α ∈ [0,1] denote the desired ratio, this generalises the PPA-complete consensus-halving problem, in which α = 1/2. Stromquist and Woodall [Stromquist and Woodall, 1985] showed that for any α, there exists a solution using 2n cuts of the segment. They also showed that if α is irrational, that upper bound is almost optimal. In this work, we elaborate the bounds for rational values α. For α = ?/k, we show a lower bound of (k-1)/k ⋅ 2n - O(1) cuts; we also obtain almost matching upper bounds for a large subset of rational α.
On the computational side, we explore its dependence on the number of cuts available. More specifically,
1) when using the minimal number of cuts for each instance is required, the problem is NP-hard for any α;
2) for a large subset of rational α = ?/k, when (k-1)/k ⋅ 2n cuts are available, the problem is in PPA-k under Turing reduction;
3) when 2n cuts are allowed, the problem belongs to PPA for any α; more generally, the problem belong to PPA-p for any prime p if 2(p-1)⋅⌈p/2⌉/⌊p/2⌋ ⋅ n cuts are available.

BibTeX - Entry

@InProceedings{goldberg_et_al:LIPIcs.ITCS.2023.57,
  author =	{Goldberg, Paul and Li, Jiawei},
  title =	{{Consensus Division in an Arbitrary Ratio}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{57:1--57:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17560},
  URN =		{urn:nbn:de:0030-drops-175606},
  doi =		{10.4230/LIPIcs.ITCS.2023.57},
  annote =	{Keywords: Consensus Halving, TFNP, PPA-k, Necklace Splitting}
}

Keywords: Consensus Halving, TFNP, PPA-k, Necklace Splitting
Collection: 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Issue Date: 2023
Date of publication: 01.02.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI