3-partitioning problems for maximizing the minimum load. (English) Zbl 1058.90025
Summary: 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.