SEMI ONLINE 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 equivale nt to minimizing the makespan on two identical machines, is known with worst-case ratio 12/11, no deterministic heuristic for the on-line pr oblem can have a worst-case ratio lower than 3/2 In this paper we inve stigate 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 a vailable which assign each item independently to the partition sets. T he 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 vers ion we propose a heuristic and investigate its worst-case ratio. All a lgorithms have a worst-case ratio of which is shown to be the best pos sible worst-case ratio. (C) 1997 Elsevier Science B.V. All rights rese rved.