Complexity Results on a Paint Shop Problem
Epping, Thomas and Hochstättler, Winfried and Oertel, Peter
(2004)
Complexity Results on a Paint Shop Problem.
Published in:
Discrete Applied Mathematics Vol. 136 (2-3).
pp. 217-226.
Abstract
Motivated by an application in the automobile industry, we present results and conjectures on a new combinatorial problem: Given a word w and restricted reservoirs of colored letters, synthesize w with a minimal number of color changes. We present a dynamic program that solves this problem and runs in polynomial time if we bound both, the number of different letters and colors. Otherwise, the problem is shown to be NP-complete. Additionally, we focus on upper bounds on the minimal number of color changes, simultaneously giving results for special instances, and posing open questions.
Download: |
Download (212kB) | Preview |
---|---|
Download: |
Download (225kB) | Preview |
Editorial actions: | ![]() |
ZAIK Number: | zaik2002-434 |
---|---|
Depositing User: | Thomas Epping |
Date Deposited: | 06 Jun 2002 00:00 |
Last Modified: | 12 Jan 2012 10:56 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/434 |