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

DOI10.1016/J.DAM.2020.05.028MaRDI QIDQ1983103zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Greedy colorings for the binary paintshop problem
• The Approximability of the Binary Paintshop Problem
• Some heuristics for the binary paint shop problem and their expected number of colour changes
• An optimal greedy heuristic to color interval graphs
• A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations
• Semi-greedy heuristics: An empirical study
• Greedy and heuristic algorithms for codes and colorings
• A heuristic for the convex recoloring problem in graphs
• A unified way of analyzing some greedy algorithms

Cites work

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

Cited in

(5)

• Improved bounds for the binary paint shop problem
• Greedy colorings of words
• Some heuristics for the binary paint shop problem and their expected number of colour changes
• Greedy colorings for the binary paintshop problem
• The Approximability of the Binary Paintshop Problem

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

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