The complexity of splitting necklaces and bisecting ham sandwiches

DOI10.1145/3313276.3316334zbMath1433.68157arXiv1805.12559OpenAlexW2963674652MaRDI QIDQ5212805

Aris Filos-Ratsikas, Paul W. Goldberg

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1805.12559

zbMATH Keywords

necklace splittingham sandwichPPA-completenessconsensus halving

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Related Items

Consensus-Halving: Does It Ever Get Easier?, A survey of mass partitions, Fixed-Parameter Algorithms for the Kneser and Schrijver Problems, Unnamed Item, Unnamed Item, Computing exact solutions of consensus halving and the Borsuk-Ulam theorem, The Hairy Ball problem is PPAD-complete, The classes PPA-\(k\): existence from arguments modulo \(k\), Arc-routing for winter road maintenance, The classes PPA-\(k\): existence from arguments modulo \(k\), Unnamed Item, The complexity of the parity argument with potential, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, The complexity of finding fair independent sets in cycles, Two's company, three's a crowd: consensus-halving for a constant number of agents, No-dimensional Tverberg theorems and algorithms, Consensus Halving for Sets of Items, Ranking binary unlabelled necklaces in polynomial time