Deligkas, Argyrios, Fearnley, John, Hollender, Alexandros and Melissourgos, Themistoklis
(2022)
Constant Inapproximability for PPA.
In: STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing.
Text
constant_epsilon_Consensus_Halving.pdf - Author Accepted Manuscript Download (675kB) | Preview |
Abstract
In the ϵ-Consensus-Halving problem, we are given n probability measures v1, ..., vn on the interval R = [0,1], and the goal is to partition R into two parts R+ and R- using at most n cuts, so that |vi(R+)-vi(R-)| ≤ ϵ for all i. This fundamental fair division problem was the first natural problem shown to be complete for the class PPA, and all subsequent PPA-completeness results for other natural problems have been obtained by reducing from it. We show that ϵ-Consensus-Halving is PPA-complete even when the parameter ϵ is a constant. In fact, we prove that this holds for any constant ϵ < 1/5. As a result, we obtain constant inapproximability results for all known natural PPA-complete problems, including Necklace-Splitting, the Discrete-Ham-Sandwich problem, two variants of the pizza sharing problem, and for finding fair independent sets in cycles and paths.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Uncontrolled Keywords: | TFNP, PPA, fair division, consensus halving, ham sandwich theorem |
Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
Depositing User: | Symplectic Admin |
Date Deposited: | 07 Mar 2022 16:23 |
Last Modified: | 24 Nov 2023 03:00 |
DOI: | 10.1145/3519935.3520079 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3150309 |