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...
| Autori principali: | , , , |
|---|---|
| Natura: | Journal article |
| Lingua: | English |
| Pubblicazione: |
Society for Industrial and Applied Mathematics
2025
|