An approximation algorithm for the cutting-sticks problem

摘要

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~(1/2).