Semi on-line algorithms for the partition problem

Semi on-line algorithms for the partition problem

0.00 Avg rating0 Votes
Article ID: iaor2002907
Country: Netherlands
Volume: 21
Issue: 5
Start Page Number: 235
End Page Number: 242
Publication Date: Dec 1997
Journal: Operations Research Letters
Authors: , , ,
Keywords: networks: scheduling
Abstract:

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 4/3 which is shown to be the best possible worst-case ratio.

Reviews

Required fields are marked *. Your email address will not be published.