3-Partitioning Problems for Maximizing the Minimum Load
Source: Journal of Combinatorial Optimization, Volume 6, Number 1, March 2002 , pp. 67-80(14)
Abstract:The optimization versions of the 3-Partitioning and the Kernel 3-Partitioning problems are considered in this paper. For the objective to maximize the minimum load of the m subsets, it is shown that the MODIFIED LPT algorithm has performance ratios (3m - 1)/(4m - 2) and (2m - 1)/(3m - 2), respectively, in the worst case.
Document Type: Regular Paper
Affiliations: 1: Department of Mathematics, Zhejiang University, Hangzhou 310027, People's Republic of China 2: Department of Mathematics, Zhejiang University, Hangzhou 310027, People's Republic of China. email@example.com 3: Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada T6G 2E8; Department of Computer Science, University of Waterloo; Department of Computing and Software, McMaster University. firstname.lastname@example.org
Publication date: March 1, 2002