Constant Inapproximability for PPA
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910709281980416 |
|---|---|
| author | Deligkas, Argyrios Fearnley, John Hollender, Alexandros Melissourgos, Themistoklis |
| author_facet | Deligkas, Argyrios Fearnley, John Hollender, Alexandros Melissourgos, Themistoklis |
| contents | In the $\varepsilon$-Consensus-Halving problem, we are given $n$ probability measures $v_1, \dots, v_n$ 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 $|v_i(R^+) - v_i(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2201_10011 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Constant Inapproximability for PPA Deligkas, Argyrios Fearnley, John Hollender, Alexandros Melissourgos, Themistoklis Computational Complexity Computer Science and Game Theory In the $\varepsilon$-Consensus-Halving problem, we are given $n$ probability measures $v_1, \dots, v_n$ 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 $|v_i(R^+) - v_i(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. |
| title | Constant Inapproximability for PPA |
| topic | Computational Complexity Computer Science and Game Theory |
| url | https://arxiv.org/abs/2201.10011 |