The approximability of the binary paintshop problem

Anupam Gupta; Satyen Kale; Viswanath Nagarajan; Rishi Saket; Baruch Schieber

doi:10.1007/978-3-642-40328-6_15

The approximability of the binary paintshop problem

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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].

Original language	English (US)
Title of host publication	Approximation, Randomization, and Combinatorial Optimization
Subtitle of host publication	Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings
Pages	205-217
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-642-40328-6_15
State	Published - 2013
Event	16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013 and the 17th International Workshop on Randomization and Computation, RANDOM 2013 - Berkeley, CA, United States Duration: Aug 21 2013 → Aug 23 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8096 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013 and the 17th International Workshop on Randomization and Computation, RANDOM 2013
Country/Territory	United States
City	Berkeley, CA
Period	8/21/13 → 8/23/13

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Gupta, A., Kale, S., Nagarajan, V., Saket, R., & Schieber, B. (2013). The approximability of the binary paintshop problem. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings (pp. 205-217). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8096 LNCS). https://doi.org/10.1007/978-3-642-40328-6_15

The approximability of the binary paintshop problem. / Gupta, Anupam; Kale, Satyen; Nagarajan, Viswanath et al.
Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings. 2013. p. 205-217 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8096 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Gupta, A, Kale, S, Nagarajan, V, Saket, R & Schieber, B 2013, The approximability of the binary paintshop problem. in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8096 LNCS, pp. 205-217, 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013 and the 17th International Workshop on Randomization and Computation, RANDOM 2013, Berkeley, CA, United States, 8/21/13. https://doi.org/10.1007/978-3-642-40328-6_15

Gupta A, Kale S, Nagarajan V, Saket R, Schieber B. The approximability of the binary paintshop problem. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings. 2013. p. 205-217. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-40328-6_15

Gupta, Anupam ; Kale, Satyen ; Nagarajan, Viswanath et al. / The approximability of the binary paintshop problem. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings. 2013. pp. 205-217 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{11de02adb078416cb4e9aabeafb3be6a,

title = "The approximability of the binary paintshop problem",

abstract = "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].",

author = "Anupam Gupta and Satyen Kale and Viswanath Nagarajan and Rishi Saket and Baruch Schieber",

year = "2013",

doi = "10.1007/978-3-642-40328-6_15",

language = "English (US)",

isbn = "9783642403279",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "205--217",

booktitle = "Approximation, Randomization, and Combinatorial Optimization",

note = "16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013 and the 17th International Workshop on Randomization and Computation, RANDOM 2013 ; Conference date: 21-08-2013 Through 23-08-2013",

}

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

Y1 - 2013

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 -

The approximability of the binary paintshop problem

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this