| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10331881 | Information Processing Letters | 2015 | 5 Pages |
Abstract
The cuttings-sticks problem is the following. We are given a bundle of sticks all having integer lengths. The total sum of their lengths is n(n+1)/2. Can we break the sticks so that the resulting sticks have lengths 1,2,â¦,n? The problem is known to be NP-hard. We consider an optimization version of the problem which involves cutting the sticks and placing them into boxes. The problem has a trivial polynomial time algorithm with an approximation ratio of 2. We present a greedy algorithm that achieves an approximation ratio of 2.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jagadish M,