Greedy versus recursive greedy: uncorrelated heuristics for the binary paint shop problem
type: Item
instance of: scholarly article
title: Greedy versus recursive greedy: uncorrelated heuristics for the binary paint shop problem
zbMATH Open document ID: 1477.90077
author: Stephan Dominique Andres
published in: Discrete Applied Mathematics
publication date: 2021-09-15T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 7395722
zbMATH Keywords: binary paint shop problem
zbMATH Keywords: greedy heuristic
zbMATH Keywords: recursive greedy heuristic
zbMATH Keywords: red first heuristic
zbMATH Keywords: greedy-perfect
zbMATH Keywords: recursive-greedy-perfect
zbMATH Keywords: red-first-perfect
zbMATH Keywords: APX-hardness
MaRDI profile type: Publication
full work available at URL: j.dam.2020.05.028
OpenAlex ID: W3037466935
cites work: Greedy colorings for the binary paintshop problem
cites work: Some heuristics for the binary paint shop problem and their expected number of colour changes
cites work: Complexity results on restricted instances of a paint shop problem for words
cites work: Complexity results on a paint shop problem.
cites work: The Approximability of the Binary Paintshop Problem
cites work: On the power of unique 2-prover 1-round games
cites work: Computing solutions of the paintshop-necklace problem
cites work: Paintshop, odd cycles and necklace splitting
cites work: Greedy colorings of words
DOI: 10.1016/J.DAM.2020.05.028
Recommended article: Greedy colorings for the binary paintshop problem
Recommended article: The Approximability of the Binary Paintshop Problem
Recommended article: Some heuristics for the binary paint shop problem and their expected number of colour changes
Recommended article: An optimal greedy heuristic to color interval graphs
Recommended article: A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations
Recommended article: Semi-greedy heuristics: An empirical study
Recommended article: Greedy and heuristic algorithms for codes and colorings
Recommended article: A heuristic for the convex recoloring problem in graphs
Recommended article: A unified way of analyzing some greedy algorithms
description: scientific article; zbMATH DE number 7395722