Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

Complexity results for restricted instances of a paint shop problem

Share/Save/Bookmark

Bonsma, P.S. (2003) Complexity results for restricted instances of a paint shop problem. [Report]

[img]
Preview
PDF
130Kb
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
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65866
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 213735