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

DOI10.1007/S11766-008-0101-8zbMATH Open1150.90009OpenAlexW1999302211MaRDI QIDQ933069FDOQ933069

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

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

zbMATH Keywords

lower boundpartitioningworst case ratioconstrained partition

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• 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
• Approximation algorithms for \(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)