An analysis of the LPT algorithm for the max-min and the min-ratio partition problems

DOI10.1016/J.TCS.2005.08.032zbMath1086.68149OpenAlexW2057299700MaRDI QIDQ817816

Bang Ye Wu

Publication date: 20 March 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.08.032

zbMATH Keywords

partitionapproximation algorithmoptimization problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation algorithms (68W25) Ramsey theory (05D10)

Related Items (1)

A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines

Cites Work

• Unnamed Item
• A tight upper bound for the \(k\)-partition problem on ideal sets
• Tighter bounds on a heuristic for a partition problem
• The modified differencing method for the set partitioning problem with cardinality constraints
• The Asymptotic Optimality of the LPT Rule
• Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics
• Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling
• Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation
• Algorithms for Scheduling Independent Tasks
• Bounds on Multiprocessing Timing Anomalies

This page was built for publication: An analysis of the LPT algorithm for the max-min and the min-ratio partition problems