Computing solutions of the paintshop-necklace problem

DOI10.1016/J.COR.2012.01.014MaRDI QIDQ1761213zbMATH OpenOpenAlexFDO

Authors Frédéric Meunier, Bertrand Neveu

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

zbMATH Keywords

combinatorial optimizationinteger programminglocal searchpaintshop problempath-following methodsplitting necklaceTFNP problem

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Integer programming (90C10) Combinatorial optimization (90C27)

Recommendations

• Paintshop, odd cycles and necklace splitting
• scientific article; zbMATH DE number 496046
• Splitting necklaces
• Bisection of Circle Colorings
• Greedy colorings for the binary paintshop problem

Cites work

• Algorithmic construction of sets for k -restrictions
• Bisection of Circle Colorings
• Combinatorial properties of certain simplicial and cubical vertex maps
• Complexity results on a paint shop problem.
• Complexity results on restricted instances of a paint shop problem for words
• Discrete splittings of the necklace
• Greedy colorings for the binary paintshop problem
• Homotopy theory of graphs
• scientific article; zbMATH DE number 66612 (Why is no real title available?)
• scientific article; zbMATH DE number 956793 (Why is no real title available?)
• Necklace bisection with one cut less than needed
• On the complexity of the parity argument and other inefficient proofs of existence
• Paintshop, odd cycles and necklace splitting
• Principles and Practice of Constraint Programming – CP 2004
• Some heuristics for the binary paint shop problem and their expected number of colour changes
• Splitting necklaces
• The Approximation of Fixed Points of a Continuous Mapping
• The Borsuk--Ulam-property, Tucker-property and constructive proofs in combinatorics
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• The complexity of finding Nash equilibria
• 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

Cited in

(10)

• Paintshop, odd cycles and necklace splitting
• Complexity results on a paint shop problem.
• Greedy versus recursive greedy: uncorrelated heuristics for the binary paint shop problem
• Upper bounds for the necklace folding problems
• Bisection of Circle Colorings
• scientific article; zbMATH DE number 5688296 (Why is no real title available?)
• scientific article; zbMATH DE number 6161631 (Why is no real title available?)
• MaxFlow-MinCut duality for a paint shop problem
• The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
• Improved bounds for the binary paint shop problem

Describes a project that uses

Uses Software

• INCOP

This page was built for publication: Computing solutions of the paintshop-necklace problem

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