Greedy versus recursive greedy: uncorrelated heuristics for the binary paint shop problem

DOI10.1016/j.dam.2020.05.028zbMath1477.90077OpenAlexW3037466935MaRDI QIDQ1983103

Stephan Dominique Andres

Publication date: 15 September 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2020.05.028

zbMATH Keywords

APX-hardnessgreedy heuristicbinary paint shop problemgreedy-perfectrecursive greedy heuristicrecursive-greedy-perfectred first heuristicred-first-perfect

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• Greedy colorings of words
• Some heuristics for the binary paint shop problem and their expected number of colour changes
• Paintshop, odd cycles and necklace splitting
• Complexity results on a paint shop problem.
• Computing solutions of the paintshop-necklace problem
• Greedy colorings for the binary paintshop problem
• Complexity results on restricted instances of a paint shop problem for words
• The Approximability of the Binary Paintshop Problem
• On the power of unique 2-prover 1-round games

This page was built for publication: Greedy versus recursive greedy: uncorrelated heuristics for the binary paint shop problem