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

DOI10.1007/s11766-008-0101-8zbMath1150.90009OpenAlexW1999302211MaRDI QIDQ933069

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

partitioninglower boundworst case ratioconstrained partition

Mathematics Subject Classification ID

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

Related Items (3)

Approximation algorithms for \(k\)-partitioning problems with partition matroid constraint ⋮ Optimal matroid partitioning problems ⋮ Unnamed Item

Cites Work

• Unnamed Item
• 3-partitioning problems for maximizing the minimum load
• Lower bounds and heuristic algorithms for the \(k_i\)-partitioning problem
• The exact LPT-bound for maximizing the minimum completion time
• The \(k\)-partitioning problem
• A tight bound for 3-partitioning
• \(\kappa\)-partitioning problems for maximizing the minimum load
• On uniform \(k\)-partition problems
• Optimal Set Partitioning
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• Bounds on Multiprocessing Timing Anomalies
• Bounds for the cardinality constrained \(P \|C_{max}\) problem

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