1. κ-Partitioning problems for maximizing the minimum load
- Author
-
He, Yong, Tan, Zhiyi, Zhu, Jing, and Yao, Enyu
- Subjects
- *
REGRESSION analysis , *ALGORITHMS , *ALGEBRA , *MATHEMATICAL optimization , *MATHEMATICAL analysis - Abstract
The optimization versions of the k-PARTITIONING problems are considered in this paper. For the objective to maximize the minimum load of m subsets, we first show that the FOLDING algorithm has a tight worst case ratio of max{2/k,1/m}. Then, we present an algorithm called HARMONIC1 with a worst case ratio at least
max{ 1/k, 1/(⌈Σi=1m 1/i ⌉ +1)} . It concludes the HARMONIC1 is better than FOLDING fork > 2(⌈ Σi=1m 1/i ⌉ + 1). We further show that HARMONICI is asymptotically optimal ordinal algorithm. We also present an algorithm HARMONIC2 for solving the generalκi-PARTITIONING problem. [Copyright &y& Elsevier]- Published
- 2003
- Full Text
- View/download PDF