Paper Info
Title
Complexity of the stamp folding problem
Abstract
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 NPcomplete. 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 in O(n2(n+k/ k)) n time where n is the number of creases and k is the total crease width. That is, the algorithm runs in O(nk+2) time for a constant k. Hence we can solve the problem eæciently for a small constant k.
Year
DOI
Venue
2011
10.1007/978-3-642-22616-8_25
COCOA
Keywords
Field
DocType
hinged paper segment,long paper strip,minimization problem,optimization problem,maximum crease width,equidistant crease,stamp folding problem,crease point,crease width,total crease width,linkage,np complete
Minimization problem,Equidistant,Discrete mathematics,NP-complete,Combinatorics,Counting problem,Minification,Time complexity,Optimization problem,Mathematics,Computational complexity theory
Conference
Volume
ISSN
Citations 
6831
0302-9743
1
PageRank 
References 
Authors
0.44
4
4
Name
Order
Citations
PageRank
Takuya Umesato120.87
Toshiki Saitoh28714.95
Ryuhei Uehara352875.38
Hiro Ito429039.95