| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10334265 | Theoretical Computer Science | 2005 | 13 Pages |
Abstract
Given a set of positive numbers, the max-min partition problem asks for a k-partition such that the minimum part is maximized. The min-ratio partition problem has the similar definition but the objective is to minimize the ratio of the maximum to the minimum parts. In this paper, we analyze the performances of the longest processing time (LPT) algorithm for the two problems. We show that the tight bounds of the LPT are, respectively (4k-2)/(3k-1) and 75.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Bang Ye Wu,