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: | Filos-Ratsikas, A, Goldberg, PW |
---|---|
Format: | Journal article |
Language: | English |
Published: |
Society for Industrial and Applied Mathematics
2022
|
Similar Items
-
The complexity of splitting necklaces and bisecting ham sandwiches
by: Filos-Ratsikas, A, et al.
Published: (2019) -
The complexity of splitting necklaces and bisecting ham sandwiches
by: Filos-Ratsikas, A, et al.
Published: (2019) -
Consensus halving is PPA-complete
by: Filos-Ratsikas, A, et al.
Published: (2018) -
Consensus-halving: does it ever get easier?
by: Filos-Ratsikas, A, et al.
Published: (2023) -
Consensus-Halving: Does It Ever Get Easier?
by: Filos-Ratsikas, Aris, et al.
Published: (2022)