The Approximability of the Binary Paintshop Problem

DOI10.1007/978-3-642-40328-6_15MaRDI QIDQ2851858zbMATH OpenOpenAlexFDO

Authors Anupam Gupta, Satyen Kale, Viswanath Nagarajan, Rishi Saket, Baruch Schieber

Publication date 4 October 2013

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-40328-6_15

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial optimization (90C27)

Recommendations

• Greedy colorings for the binary paintshop problem
• scientific article; zbMATH DE number 6161631
• Some heuristics for the binary paint shop problem and their expected number of colour changes
• Greedy versus recursive greedy: uncorrelated heuristics for the binary paint shop problem
• Polynomial-time approximation algorithms for the coloring problem in some cases
• Algorithms and Computation
• Almost optimal solutions for bin coloring problems
• On Approximation Algorithms for # P
• Complexity results on restricted instances of a paint shop problem for words
• An approximation algorithm for the art gallery problem

Cited in

(8)

• Paintshop, odd cycles and necklace splitting
• Selecting and covering colored points
• Greedy versus recursive greedy: uncorrelated heuristics for the binary paint shop problem
• Greedy colorings for the binary paintshop problem
• Complexity results on restricted instances of a paint shop problem for words
• scientific article; zbMATH DE number 6161631 (Why is no real title available?)
• Some heuristics for the binary paint shop problem and their expected number of colour changes
• On Covering Segments with Unit Intervals

This page was built for publication: The Approximability of the Binary Paintshop Problem

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