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

DOI10.1016/J.TCS.2005.08.032zbMATH Open1086.68149OpenAlexW2057299700MaRDI QIDQ817816FDOQ817816

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

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

zbMATH Keywords

partitionapproximation algorithmoptimization problem

Mathematics Subject Classification ID

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

Cites Work

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

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)