Approximation algorithms for \(k\)-partitioning problems with partition matroid constraint

DOI10.1007/s11590-013-0637-2zbMath1292.90252OpenAlexW2052140946MaRDI QIDQ2448182

Jianping Li, Weidong Li

Publication date: 30 April 2014

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-013-0637-2

zbMATH Keywords

approximation algorithmpartition matroidefficient polynomial time approximation scheme (EPTAS)full polynomial time approximation scheme (FPTAS)

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items

Knapsack problem with objective value gaps, Optimal matroid partitioning problems, Unnamed Item

Cites Work

• 3-partitioning problems for maximizing the minimum load
• Lower bounds and heuristic algorithms for the \(k_i\)-partitioning problem
• Lower bounds and modified LPT algorithm for \(k\)-partitioning problems with partition matroid constraint
• \(k\)-partitioning problems with partition matroid constraint
• The \(k\)-partitioning problem
• A tight bound for 3-partitioning
• \(\kappa\)-partitioning problems for maximizing the minimum load
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• On uniform \(k\)-partition problems
• Integer Programming with a Fixed Number of Variables
• Bounds for the cardinality constrained \(P \|C_{max}\) problem