The Approximability of the Binary Paintshop Problem

DOI10.1007/978-3-642-40328-6_15zbMath1407.68194OpenAlexW2230145189MaRDI QIDQ2851858

Anupam Gupta, Viswanath Nagarajan, Satyen Kale, 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

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

Related Items (3)

Greedy versus recursive greedy: uncorrelated heuristics for the binary paint shop problem ⋮ Selecting and covering colored points ⋮ On Covering Segments with Unit Intervals

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