论文标题
披萨分享是ppa-hard
Pizza Sharing is PPA-hard
论文作者
论文摘要
我们研究了为直截了当和正方形的披萨共享问题找到解决方案的计算复杂性。我们表明，计算$ \ varepsilon $ -Approximate解决方案对于这两个问题都是ppa complete，而在为方形切割问题找到精确的解决方案是fixp-hard和bu中。即使所有质量分布都由非重叠的轴对准矩形或它们是点集，我们的ppa-hardness结果适用于任何$ \ varepsilon <1/5 $，即使所有质量分布都适用，即使所有质量分布都是正方形和右角的三角形，我们的固定固定结果也适用。我们还证明，这两个近似问题的决策变体都是NP完整的，而对于正方形切割披萨共享的确切版本来说，它符合ETR填充。
We study the computational complexity of finding a solution for the straight-cut and square-cut pizza sharing problems. We show that computing an $\varepsilon$-approximate solution is PPA-complete for both problems, while finding an exact solution for the square-cut problem is FIXP-hard and in BU. Our PPA-hardness results apply for any $\varepsilon < 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 it is ETR-complete for the exact version of square-cut pizza sharing.
