Deligkas, Argyrios, Fearnley, John and Melissourgos, Themistoklis
(2022)
Pizza Sharing Is PPA-Hard.
THIRTY-SIXTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FOURTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE / THE TWELVETH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, 36 (5).
pp. 4957-4965.
Text
2012.14236v1.pdf - Submitted version Download (2MB) | Preview |
Abstract
We study the computational complexity of computing solutions for the straight-cut and square-cut pizza sharing problems. We show that finding an approximate solution is PPA-hard for the straight-cut problem, and PPA-complete for the square-cut problem, while finding an exact solution for the square-cut problem is FIXP-hard and in BU. Our PPA-hardness results apply even when all mass distributions are unions of non-overlapping squares, and our FIXP-hardness result applies even when all mass distributions are unions of weighted squares and right-angled triangles. We also show that decision variants of the square-cut problem are hard: we show that the approximate problem is NP-complete, and the exact problem is ETR-complete.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | cs.CC, cs.CC, cs.CG, math.GN |
Depositing User: | Symplectic Admin |
Date Deposited: | 15 Jan 2021 09:24 |
Last Modified: | 15 Mar 2024 05:22 |
DOI: | 10.1609/aaai.v36i5.20426 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3113625 |