The complexity of the stamp folding problem
The complexity of the stamp folding problem
复制标题
邮票折叠问题的复杂性
DOI：
10.1016/j.tcs.2012.08.006
复制
发表时间：
2013
影响因子：
1.1
通讯作者：
and Yoshio Okamoto
中科院分区：
文献类型：
--
作者：
Takuya Umesato;Toshiki Saitoh;Ryuhei Uehara;Hiro Ito;and Yoshio Okamoto
对于长纸条上给定等距折痕的山谷图，有许多与该图一致的折叠状态。在这些折叠状态中，我们希望折叠一张纸，使每一对铰接的纸段之间的纸层数，即折痕点处的折痕宽度，达到最小。这个问题被称为邮票折叠问题，这个问题有两种变体；最大折痕宽度的最小化和总折痕宽度的最小化。这一优化问题是最近从计数问题的角度引入和研究的。然而，其计算复杂度尚不清楚。本文首先证明了最大折痕宽度的最小化问题是强np完全的。因此，除非P=NP，否则我们无法在多项式时间内解决问题。接下来，我们提出了一个解决最小化问题的算法。该算法本身很简单，但对其进行分析并不简单。结果表明，该算法在折痕数等于折痕总宽度的情况下运行。也就是说，对于一个常量，算法运行inO（nk+ 2）时间。因此，我们可以有效地解决一个小常数的问题。
For a given mountain-valley pattern of equidistant creases on a long paper strip, there are many folded states consistent with the pattern. Among these folded states, we like to fold a paper so that the number of the paper layers between each pair of hinged paper segments, which is called the crease width at the crease point, is minimized. This problem is called the stamp folding problem and there are two variants of this problem; minimization of the maximum crease width, and minimization of the total crease width. This optimization problem is recently introduced and investigated from the viewpoint of the counting problem. However, its computational complexity is not known. In this paper, we first show that the minimization problem of the maximum crease width is strongly NP-complete. Hence we cannot solve the problem in polynomial time unless P=NP. We next propose an algorithm that solves the minimization problem. The algorithm itself is a straightforward one, but its analysis is not trivial. We show that this algorithm runs intime wherenis the number of creases andkis the total crease width. That is, the algorithm runs inO(nk+ 2) time for a constantk. Hence we can solve the problem efficiently for a small constantk.