Some heuristics for the binary paint shop problem and their expected number of colour changes

DOI10.1016/j.jda.2010.12.003zbMath1221.68175OpenAlexW1995865530MaRDI QIDQ553962

Winfried Hochstättler, Stephan Dominique Andres

Publication date: 29 July 2011

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2010.12.003

zbMATH Keywords

greedy algorithmaverage performancepaint shop problem

Mathematics Subject Classification ID

Combinatorics on words (68R15) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Greedy colorings of words ⋮ Greedy versus recursive greedy: uncorrelated heuristics for the binary paint shop problem ⋮ Computing solutions of the paintshop-necklace problem

Cites Work

• Unnamed Item
• Approximation algorithms for the Bipartite Multicut problem
• Paintshop, odd cycles and necklace splitting
• 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

This page was built for publication: Some heuristics for the binary paint shop problem and their expected number of colour changes