A performance guarantee for the greedy set-partitioning algorithm

DOI10.1007/BF00264618zbMATH Open0535.05008OpenAlexW1964048951MaRDI QIDQ790814FDOQ790814

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

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

zbMATH Keywords

subsetsset-partitioning

Mathematics Subject Classification ID

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

Cited In (11)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Heuristic methods and applications: A categorized survey
• Title not available (Why is that?)
• Comparing the minimum completion times of two longest-first scheduling-heuristics
• Improved algorithms to minimize workload balancing criteria on identical parallel machines
• The exact LPT-bound for maximizing the minimum completion time
• A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines
• A greedy heuristic for 3-partitioning with similar elements
• Unexpected failure of a greedy choice algorithm proposed by Hoffman
• Maximizing the minimum load: the cost of selfishness

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)