Deligkas, Argyrios and Fearnley, John and Hollender, Alexandros and Melissourgos, Themistoklis (2025) Constant Inapproximability for PPA. SIAM Journal on Computing, 54 (1). pp. 163-192. DOI https://doi.org/10.1137/22M1536613
Deligkas, Argyrios and Fearnley, John and Hollender, Alexandros and Melissourgos, Themistoklis (2025) Constant Inapproximability for PPA. SIAM Journal on Computing, 54 (1). pp. 163-192. DOI https://doi.org/10.1137/22M1536613
Deligkas, Argyrios and Fearnley, John and Hollender, Alexandros and Melissourgos, Themistoklis (2025) Constant Inapproximability for PPA. SIAM Journal on Computing, 54 (1). pp. 163-192. DOI https://doi.org/10.1137/22M1536613
Abstract
In the \varepsilon -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 )| \leq \varepsilon 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 \varepsilon -Consensus- Halving is PPA-complete even when the parameter \varepsilon is a constant. In fact, we prove that this holds for any constant \varepsilon < 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: | Article |
---|---|
Uncontrolled Keywords: | TFNP; PPA; fair division; consensus halving; ham sandwich theorem |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 16 Oct 2024 12:42 |
Last Modified: | 14 Mar 2025 12:32 |
URI: | http://repository.essex.ac.uk/id/eprint/39415 |
Available files
Filename: Constant Inapproximability for PPA.pdf
Licence: Creative Commons: Attribution 4.0