The Complexity of Necklace Splitting, Consensus-Halving and Discrete Ham Sandwich
Aris Filos-Ratsikas (University of Liverpool)
Abstract: The Necklace Splitting problem and its continuous counterpart, the Consensus-Halving problem, as well as the Discrete Ham Sandwich problem, are classical problems in combinatorics, with applications to fair division and social choice theory. A distinctive characteristic of these problems is that they always have a solution, but it was not known until recently whether such a solution can be found efficiently. We study the computational complexity of these problems and show that they are complete for the computational class PPA. A direct implication of this result is that the problems are unlikely to be solvable in polynomial time.
P.S. For papers, see arxiv.org/abs/1711.04503 and arxiv.org/abs/1805.12559
Computer scienceMathematics
Audience: researchers in the discipline
LA Combinatorics and Complexity Seminar
Series comments: Password is on the seminar page. www.math.ucla.edu/~pak/seminars/CCSem-Fall-2020.htm
| Organizers: | Igor Pak*, Greta Panova |
| *contact for this listing |