Semi on-line algorithms for the partition problem

The partition problem is one of the basic NP-complete problems. While an efficient heuristic for the optimization version, which is equivalent to minimizing the makespan on two identical machines, is known with worst-case ratio 12/11, no deterministic heuristic for the on-line problem can have a worst-case ratio lower than 3/2 In this paper we investigate three different semi on-line versions of the partition problem. In the first case, we assume that a buffer of length k is available to maintain k items. In the second case, two parallel processors are available which assign each item independently to the partition sets. The best of the two produced solutions is chosen. Finally, in the third problem the total sum of the items is known in advance. For each version we propose a heuristic and investigate its worst-case ratio. All algorithms have a worst-case ratio of which is shown to be the best possible worst-case ratio. (C) 1997 Elsevier Science B.V. All rights reserved.