Constant inapproximability for PPA
<p>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...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2024
|
| _version_ | 1817931525036965888 |
|---|---|
| author | Deligkas, A Fearnley, J Hollender, A Melissourgos, T |
| author_facet | Deligkas, A Fearnley, J Hollender, A Melissourgos, T |
| author_sort | Deligkas, A |
| collection | OXFORD |
| description | <p>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.</p> |
| first_indexed | 2024-12-09T03:23:24Z |
| format | Journal article |
| id | oxford-uuid:0c4fbbb9-9705-4eac-9eea-98adbe08c3b3 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-12-09T03:23:24Z |
| publishDate | 2024 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:0c4fbbb9-9705-4eac-9eea-98adbe08c3b32024-11-25T10:01:46ZConstant inapproximability for PPAJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:0c4fbbb9-9705-4eac-9eea-98adbe08c3b3EnglishSymplectic ElementsSociety for Industrial and Applied Mathematics2024Deligkas, AFearnley, JHollender, AMelissourgos, T<p>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.</p> |
| spellingShingle | Deligkas, A Fearnley, J Hollender, A Melissourgos, T Constant inapproximability for PPA |
| title | Constant inapproximability for PPA |
| title_full | Constant inapproximability for PPA |
| title_fullStr | Constant inapproximability for PPA |
| title_full_unstemmed | Constant inapproximability for PPA |
| title_short | Constant inapproximability for PPA |
| title_sort | constant inapproximability for ppa |
| work_keys_str_mv | AT deligkasa constantinapproximabilityforppa AT fearnleyj constantinapproximabilityforppa AT hollendera constantinapproximabilityforppa AT melissourgost constantinapproximabilityforppa |