The complexity of necklace splitting, consensus-halving, and discrete ham sandwich
We resolve the computational complexity of three problems known as Necklace Splitting, Consensus-Halving, and Discrete Ham sandwich, showing that they are PPA-complete. For NECKLACE SPLITTING, this result is specific to the important special case in which two thieves share the necklace. These are th...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2022
|