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

@

Journal of Information Science and Engineering, Vol. 23 No. 2, pp. 641-647 (March 2007)

Performances of List Scheduling for Set Partition Problems*

Bang Ye Wu and Hsiu-Hui Ou
Department of Computer Science and Information Engineering
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

Full Text () 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.