The complexity of splitting necklaces and bisecting ham sandwiches
From MaRDI portal
Publication:5212805
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
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
