Computing solutions of the paintshop-necklace problem
From MaRDI portal
Publication:1761213
DOI10.1016/j.cor.2012.01.014zbMath1251.90250MaRDI QIDQ1761213
Bertrand Neveu, Frédéric Meunier
Publication date: 15 November 2012
Published in: Computers \& Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cor.2012.01.014
integer programming; combinatorial optimization; local search; path-following method; paintshop problem; splitting necklace; TFNP problem
90C10: Integer programming
90C27: Combinatorial optimization
90B80: Discrete location and assignment
Related Items
The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich, Greedy versus recursive greedy: uncorrelated heuristics for the binary paint shop problem
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Some heuristics for the binary paint shop problem and their expected number of colour changes
- Necklace bisection with one cut less than needed
- Paintshop, odd cycles and necklace splitting
- Splitting necklaces
- On the complexity of the parity argument and other inefficient proofs of existence
- Complexity results on a paint shop problem.
- Greedy colorings for the binary paintshop problem
- Complexity results on restricted instances of a paint shop problem for words
- The Borsuk--Ulam-property, Tucker-property and constructive proofs in combinatorics
- Homotopy theory of graphs
- Combinatorial properties of certain simplicial and cubical vertex maps
- Algorithmic construction of sets for k -restrictions
- Discrete Splittings of the Necklace
- Bisection of Circle Colorings
- The Borsuk-Ulam Theorem and Bisection of Necklaces
- The Approximation of Fixed Points of a Continuous Mapping
- Principles and Practice of Constraint Programming – CP 2004
- Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
