A Paint Shop Problem for Words
Epping, Thomas and Hochstättler, Winfried and Oertel, Peter
(2000)
A Paint Shop Problem for Words.
Technical Report
, 7 p.
Abstract
Motivated by an application in the automobile industry, we present results on the following problem: Given a word w=(w_1,ldots,w_n) and a color vector f=(f_1,ldots,f_n) with f_i denoting the color of w_i, find a permutation sigma in mathcal{S}_n such that w_{sigma(i)}=w_i and the number of color changes within sigma(f)=(f_{sigma(1)},ldots,f_{sigma(n)}) is minimized. We show that this problem is polynomially solvable if we bound both, the number of letters and the number of colors, and becomes NP-complete otherwise.
Actions:
Download: |
Download (156kB) | Preview |
---|---|
Download: |
Download (159kB) | Preview |
Editorial actions: | ![]() |
Content information:
Item Type: | Paper (Technical Report) |
---|---|
Citations: | 3 (Google Scholar) | |
Uncontrolled Keywords: | assembly line dynamic programming NP-completeness Paint Shop sequencing |
Subjects: | |
Divisions: | Institute of Computer Science > Computer Science Department - Prof. Dr. Schrader Mathematical Institute > Prof. Dr. Faigle |
Related URLs: |
Deposit Information:
ZAIK Number: | zaik2000-395 |
---|---|
Depositing User: | Thomas Epping |
Date Deposited: | 20 Jun 2001 00:00 |
Last Modified: | 16 Jan 2012 13:50 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/395 |