TY - GEN

T1 - The approximability of the binary paintshop problem

AU - Gupta, Anupam

AU - Kale, Satyen

AU - Nagarajan, Viswanath

AU - Saket, Rishi

AU - Schieber, Baruch

PY - 2013/10/15

Y1 - 2013/10/15

N2 - In the Binary Paintshop problem, there are m cars appearing in a sequence of length 2m, with each car occurring twice. Each car needs to be colored with two colors. The goal is to choose for each car, which of its occurrences receives either color, so as to minimize the total number of color changes in the sequence. We show that the Binary Paintshop problem is equivalent (up to constant factors) to the Minimum Uncut problem, under randomized reductions. By derandomizing this reduction for hard instances of the Min Uncut problem arising from the Unique Games Conjecture, we show that the Binary Paintshop problem is ω(1)-hard to approximate (assuming the UGC). This answers an open question from [BEH06,MS09,AH11].

AB - In the Binary Paintshop problem, there are m cars appearing in a sequence of length 2m, with each car occurring twice. Each car needs to be colored with two colors. The goal is to choose for each car, which of its occurrences receives either color, so as to minimize the total number of color changes in the sequence. We show that the Binary Paintshop problem is equivalent (up to constant factors) to the Minimum Uncut problem, under randomized reductions. By derandomizing this reduction for hard instances of the Min Uncut problem arising from the Unique Games Conjecture, we show that the Binary Paintshop problem is ω(1)-hard to approximate (assuming the UGC). This answers an open question from [BEH06,MS09,AH11].

UR - http://www.scopus.com/inward/record.url?scp=84885215249&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84885215249&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-40328-6_15

DO - 10.1007/978-3-642-40328-6_15

M3 - Conference contribution

AN - SCOPUS:84885215249

SN - 9783642403279

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 205

EP - 217

BT - Approximation, Randomization, and Combinatorial Optimization

T2 - 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013 and the 17th International Workshop on Randomization and Computation, RANDOM 2013

Y2 - 21 August 2013 through 23 August 2013

ER -