Previous | [ 1] | [ 2] | [ 3] | [ 4] | [ 5] | [ 6] | [ 7] | [ 8] | [ 9] | [ 10] | [ 11] | [ 12] | [ 13] | [ 14] | [ 15] | [ 16] | [ 17] | [ 18] | [ 19] | [ 20] |

¡@

**Bang Ye Wu and Hsiu-Hui Ou**

Shu-Te University

Kaohsiung, 824 Taiwan

E-mail: bangye@mail.stu.edu.tw

An *m*-partition of a set is a way to distribute the members into m parts. Given a set
of positive numbers, an optimal *m*-partition problem asks for an *m*-partition optimizing
some objective function. List scheduling is an on-line algorithm that has been widely
used in scheduling problems. In this paper, we show the tight bounds on the performances
of list scheduling for partition problems with the following objective functions:
maximizing the minimum part, maximizing the sum of the smallest *k* parts, minimizing
the sum of the largest k parts, and minimizing the ratio of the largest to the smallest part,
in which 1 <= *k* < *m*.

*
Keywords:
*
analysis of algorithms, approximation algorithms, list scheduling, partitions, optimization problems

Retrieve PDF document (**200703_18.pdf**)

Received March 10, 2005; revised June 9, 2005; accepted June 20, 2005.

Communicated by Gen-Huey Chen.
^{*} This work was supported in part by the National Science Council of Taiwan, R.O.C., under grant No.
93-2213-E-366-014.