A performance guarantee for the greedy set-partitioning algorithm

DOI10.1007/BF00264618MaRDI QIDQ790814zbMATH OpenOpenAlexFDO

Authors E. G. jun. Coffman, Michael A. Langston

Publication date 1984

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00264618

zbMATH Keywords

set-partitioningsubsets

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial aspects of partitions of integers (05A17) Elementary theory of partitions (11P81)

Review text

Let S be a set of positive numbers and m an integer not less than 2. The problem is to partition S into m subsets such that the ratio of the largest set to the smallest set is as small as possible. Let \(\rho_ g(S)\) be the value of this ratio using the greedy or largest-first rule and \(\rho_ 0(S)\) be the smallest possible value of this ratio, i.e., the optimal value. The authors prove that \(\rho_ g(S)/\rho_ 0(S)\leq 7/5,\) and that this is a best possible bound for all m.

Recommendations

• Partitioning ideal sets
• Computer-assisted proof of performance ratios for the differencing method
• scientific article; zbMATH DE number 1962846
• Partitioning under the \(L_p\) norm
• scientific article; zbMATH DE number 1112368

Cited in

(12)

• The exact LPT-bound for maximizing the minimum completion time
• Improved algorithms to minimize workload balancing criteria on identical parallel machines
• Heuristic methods and applications: A categorized survey
• Comparing the minimum completion times of two longest-first scheduling-heuristics
• scientific article; zbMATH DE number 4130003 (Why is no real title available?)
• A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines
• Maximizing the minimum load: the cost of selfishness
• scientific article; zbMATH DE number 1962846 (Why is no real title available?)
• scientific article; zbMATH DE number 1543054 (Why is no real title available?)
• Unexpected failure of a greedy choice algorithm proposed by Hoffman
• A greedy heuristic for 3-partitioning with similar elements
• Approximation schemes for k-subset sum ratio and k-way number partitioning ratio

This page was built for publication: A performance guarantee for the greedy set-partitioning algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q790814)