Consensus division in an arbitrary ratio

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 α = 12. Stromquist and Woodall [30]...

Full beskrivning

Bibliografiska uppgifter
Huvudupphovsmän: Goldberg, P, Li, J
Materialtyp: Conference item
Språk:English
Publicerad: Schloss Dagstuhl – Leibniz-Zentrum für Informatik 2023
_version_ 1826315158809477120
author Goldberg, P
Li, J
author_facet Goldberg, P
Li, J
author_sort Goldberg, P
collection OXFORD
description 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 α = 12. Stromquist and Woodall [30] 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−k1 · 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−k1 · 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/p/22⌋⌉ · n cuts are available.
first_indexed 2024-12-09T03:20:38Z
format Conference item
id oxford-uuid:b4a0b73e-2e2c-48b8-bfe7-129ef6b80e5c
institution University of Oxford
language English
last_indexed 2024-12-09T03:20:38Z
publishDate 2023
publisher Schloss Dagstuhl – Leibniz-Zentrum für Informatik
record_format dspace
spelling oxford-uuid:b4a0b73e-2e2c-48b8-bfe7-129ef6b80e5c2024-11-06T16:07:02ZConsensus division in an arbitrary ratioConference itemhttp://purl.org/coar/resource_type/c_5794uuid:b4a0b73e-2e2c-48b8-bfe7-129ef6b80e5cEnglishSymplectic Elements Schloss Dagstuhl – Leibniz-Zentrum für Informatik2023Goldberg, PLi, JWe 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 α = 12. Stromquist and Woodall [30] 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−k1 · 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−k1 · 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/p/22⌋⌉ · n cuts are available.
spellingShingle Goldberg, P
Li, J
Consensus division in an arbitrary ratio
title Consensus division in an arbitrary ratio
title_full Consensus division in an arbitrary ratio
title_fullStr Consensus division in an arbitrary ratio
title_full_unstemmed Consensus division in an arbitrary ratio
title_short Consensus division in an arbitrary ratio
title_sort consensus division in an arbitrary ratio
work_keys_str_mv AT goldbergp consensusdivisioninanarbitraryratio
AT lij consensusdivisioninanarbitraryratio