Pizza Sharing is PPA-hard
Open Access
- 21 April 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
Abstract
We study the computational complexity of finding a solution for the straight-cut and square-cut pizza sharing problems. We show that computing an ε-approximate solution is PPA -complete for both problems, while finding an exact solution for the square-cut problem is FIXP -hard. Our PPA -hardness results apply for any ε < 1/5, even when all mass distributions consist of non-overlapping axis-aligned rectangles or when they are point sets, and our FIXP -hardness result applies even when all mass distributions are unions of squares and right-angled triangles. We also prove that the decision variants of both approximate problems are NP -complete, while the decision variant for the exact version of square-cut pizza sharing is \(\exists \mathbb {R} \) -complete.
Keywords
This publication has 42 references indexed in Scilit:
- The Complexity of Finding Fair Independent Sets in Cyclescomputational complexity, 2022
- Complexity of Some Geometric and Topological Problems2010
- A fair division solution to the problem of redistrictingSocial Choice and Welfare, 2008
- Using the Borsuk–Ulam Theorem2008
- Existential Theory of the Reals2006
- Discrete Geometry on Red and Blue Points in the Plane — A Survey —2003
- Lectures on Discrete Geometry2002
- Algorithms in Combinatorial Geometry1987
- Data Structures and Algorithms 31984
- ber Abbildung von MannigfaltigkeitenMathematische Annalen, 1911