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

DOI10.1016/J.TCS.2005.08.032MaRDI QIDQ817816zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Investigation of maximum and minimum satisfiability problems using \(L\)-partition
• A polynomial-time algorithm for max-min partitioning of ladders
• Analysis and solving SAT and MAX-SAT problems using an L-partition approach
• Analysis of Lagrangian Lower Bounds for a Graph Partitioning Problem
• Analysis of algorithms for a class of continuous partition problems
• Analysis of the knapsack problem using L-partition
• Approximation Algorithms for the Minimum Convex Partition Problem
• An improved approximation algorithm for the minimum common integer partition problem
• An improved approximation algorithm for the minimum common integer partition problem
• Approximation Algorithms for Min–Max Tree Partition

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A tight upper bound for the \(k\)-partition problem on ideal sets
• Algorithms for Scheduling Independent Tasks
• Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling
• Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics
• Bounds on Multiprocessing Timing Anomalies
• The Asymptotic Optimality of the LPT Rule
• The modified differencing method for the set partitioning problem with cardinality constraints
• Tighter bounds on a heuristic for a partition problem
• Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation

Cited in

(4)

• Investigation of maximum and minimum satisfiability problems using \(L\)-partition
• A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines
• Lower bounds and modified LPT algorithm for \(k\)-partitioning problems with partition matroid constraint
• Partitioning under the \(L_p\) norm

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

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