Complexity results for restricted instances of a paint shop problem

P.S. Bonsma

Complexity results for restricted instances of a paint shop problem

P.S. Bonsma

Discrete Mathematics and Mathematical Programming

Research output: Book/Report › Report › Professional

27 Downloads (Pure)

Abstract

We study the following problem: an instance is a word with every letter occurring twice. A solution is a 2-coloring of the letters in the word such that the two occurrences of every letter are colored with different colors. The goal is to minimize the number of color changes between adjacent letters. This is a special case of the Paint Shop Problem, which was previously shown to be $\mathcal{NP}$-hard. We show that this special case is also $\mathcal{NP}$-hard and even $\mathcal{APX}$-hard

Original language	Undefined
Place of Publication	Enschede
Publisher	University of Twente, Department of Applied Mathematics
Number of pages	7
ISBN (Print)	0169-2690
Publication status	Published - 2003

Publication series

Name	Memorandum Afdeling TW
Publisher	Department of Applied Mathematics, University of Twente
No.	1681
ISSN (Print)	0169-2690

Keywords

IR-65866
METIS-213735
MSC-68R15
MSC-90B30
EWI-3501
MSC-68Q25

Access to Document

1681
open
1681
open

Cite this

Bonsma, P. S. (2003). Complexity results for restricted instances of a paint shop problem. (Memorandum Afdeling TW; No. 1681). Enschede: University of Twente, Department of Applied Mathematics.

@book{51296c77d7bd4dd38634cf0cc7e2c359,

title = "Complexity results for restricted instances of a paint shop problem",

abstract = "We study the following problem: an instance is a word with every letter occurring twice. A solution is a 2-coloring of the letters in the word such that the two occurrences of every letter are colored with different colors. The goal is to minimize the number of color changes between adjacent letters. This is a special case of the Paint Shop Problem, which was previously shown to be $\mathcal{NP}$-hard. We show that this special case is also $\mathcal{NP}$-hard and even $\mathcal{APX}$-hard",

keywords = "IR-65866, METIS-213735, MSC-68R15, MSC-90B30, EWI-3501, MSC-68Q25",

author = "P.S. Bonsma",

note = "Imported from MEMORANDA",

year = "2003",

language = "Undefined",

isbn = "0169-2690",

series = "Memorandum Afdeling TW",

publisher = "University of Twente, Department of Applied Mathematics",

number = "1681",

}

TY - BOOK

T1 - Complexity results for restricted instances of a paint shop problem

AU - Bonsma, P.S.

N1 - Imported from MEMORANDA

PY - 2003

Y1 - 2003

N2 - We study the following problem: an instance is a word with every letter occurring twice. A solution is a 2-coloring of the letters in the word such that the two occurrences of every letter are colored with different colors. The goal is to minimize the number of color changes between adjacent letters. This is a special case of the Paint Shop Problem, which was previously shown to be $\mathcal{NP}$-hard. We show that this special case is also $\mathcal{NP}$-hard and even $\mathcal{APX}$-hard

AB - We study the following problem: an instance is a word with every letter occurring twice. A solution is a 2-coloring of the letters in the word such that the two occurrences of every letter are colored with different colors. The goal is to minimize the number of color changes between adjacent letters. This is a special case of the Paint Shop Problem, which was previously shown to be $\mathcal{NP}$-hard. We show that this special case is also $\mathcal{NP}$-hard and even $\mathcal{APX}$-hard

KW - IR-65866

KW - METIS-213735

KW - MSC-68R15

KW - MSC-90B30

KW - EWI-3501

KW - MSC-68Q25

M3 - Report

SN - 0169-2690

T3 - Memorandum Afdeling TW

BT - Complexity results for restricted instances of a paint shop problem

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -