Lower bounds and modified LPT algorithm for k-partitioning problems with partition matroid constraint

DOI10.1007/S11766-008-0101-8MaRDI QIDQ933069zbMATH OpenOpenAlexFDO

Authors Biao Wu, Enyu Yao

Publication date 6 August 2008

Published in Applied Mathematics. Series B (English Edition) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11766-008-0101-8

zbMATH Keywords

lower boundpartitioningworst case ratioconstrained partition

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• \(k\)-partitioning problems with partition matroid constraint
• Approximation algorithms for \(k\)-partitioning problems with partition matroid constraint
• Min-Max partitioning problem with matroid constraint
• An analysis of the LPT algorithm for the max-min and the min-ratio partition problems
• 3-partitioning problems for maximizing the minimum load

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• 3-partitioning problems for maximizing the minimum load
• A tight bound for 3-partitioning
• Bounds for the cardinality constrained \(P \|C_{max}\) problem
• Bounds on Multiprocessing Timing Anomalies
• Lower bounds and heuristic algorithms for the \(k_i\)-partitioning problem
• On uniform \(k\)-partition problems
• Optimal Set Partitioning
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• The \(k\)-partitioning problem
• The exact LPT-bound for maximizing the minimum completion time
• \(\kappa\)-partitioning problems for maximizing the minimum load

Cited in

(6)

• Approximation algorithms for \(k\)-partitioning problems with partition matroid constraint
• Lower bounds and heuristic algorithms for the \(k_i\)-partitioning problem
• Optimal matroid partitioning problems
• Optimal matroid partitioning problems
• \(k\)-partitioning problems with partition matroid constraint
• Min-Max partitioning problem with matroid constraint

This page was built for publication: Lower bounds and modified LPT algorithm for \(k\)-partitioning problems with partition matroid constraint

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