ICAR Research Data Repository for Knowledge Management
An approximation algorithm for the cutting-sticks problem
DSpace at IIT Bombay
View Archive Info| Field | Value | |
| Title |
An approximation algorithm for the cutting-sticks problem
|
|
| Creator |
JAGADISH, M
|
|
| Subject |
Approximation algorithms
Cutting-sticks |
|
| Description |
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 root 2. (C) 2014 Elsevier B.V. All rights reserved.
|
|
| Publisher |
ELSEVIER SCIENCE BV
|
|
| Date |
2016-01-14T14:07:36Z
2016-01-14T14:07:36Z 2015 |
|
| Type |
Article
|
|
| Identifier |
INFORMATION PROCESSING LETTERS, 115(2)170-174
0020-0190 1872-6119 http://dx.doi.org/10.1016/j.ipl.2014.09.007 http://dspace.library.iitb.ac.in/jspui/handle/100/17687 |
|
| Language |
en
|
|