Efficient splitting of necklaces

DOI10.4230/LIPICS.ICALP.2021.14MaRDI QIDQ7241110zbMATH OpenFDO

Authors Noga Alon, Andrei Graur

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2021.14

zbMATH Keywords

approximation algorithmsdiscrepancynecklace halvingnecklace splittingonline algorithms

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A framework for solving VLSI graph layout problems
• A Moment Problem in L 1 Approximation
• Algorithmic construction of sets for k -restrictions
• Bisection of Circle Colorings
• Complexity results on restricted instances of a paint shop problem for words
• Consensus halving is PPA-complete
• Constructive algorithms for discrepancy minimization
• Deterministic discrepancy minimization
• Discrepancy games
• Hardness results for consensus-halving
• scientific article; zbMATH DE number 66612 (Why is no real title available?)
• scientific article; zbMATH DE number 1015852 (Why is no real title available?)
• On a distribution problem in finite and countable sets
• On the complexity of the parity argument and other inefficient proofs of existence
• On-line balancing of random inputs
• Simplotopal maps and necklace splitting
• Splitting necklaces
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• The complexity of computing a Nash equilibrium
• The complexity of equilibria: Hardness results for economies via a correspondence with games
• The complexity of splitting necklaces and bisecting ham sandwiches

This page was built for publication: Efficient splitting of necklaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241110)