Complexity results on a paint shop problem
Complexity results on a paint shop problem
复制标题
DOI：
10.1016/s0166-218x(03)00442-6
复制
发表时间：
2004-02-15
影响因子：
1.1
通讯作者：
Oertel, P
中科院分区：
文献类型：
--
作者：
Epping, T;Hochstättler, W;Oertel, P
受汽车工业应用的启发，我们给出了一个新的组合问题的结果和猜想：给定一个单词w和有限的颜色字母库，合成的w的颜色变化次数最少。我们给出了一个动态规划来解决这个问题，如果我们同时限定不同字母和颜色的个数，则该规划的运行时间是多项式的。否则，问题被证明是NP-完全的。此外，我们关注颜色变化的最小次数的上界，同时给出特殊情况的结果，并提出开放问题。(C)2003爱思唯尔B.V.保留所有权利。
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. (C) 2003 Elsevier B.V. All rights reserved.