×

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.

MSC:

90B35 Deterministic scheduling theory in operations research
68W40 Analysis of algorithms
Full Text: DOI