A 3/2-approximation algorithm for \(k_i\)-partitioning

DOI10.1016/j.orl.2011.06.005zbMath1235.90063OpenAlexW2034931448MaRDI QIDQ408403

Vladimir Kotov, Hans Kellerer

Publication date: 5 April 2012

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2011.06.005

zbMATH Keywords

schedulingparallel machinesworst-case analysispartition problem

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (6)

Operations research models for coalition structure in collaborative logistics ⋮ An Efficient PTAS for Parallel Machine Scheduling with Capacity Constraints ⋮ EPTAS for parallel identical machine scheduling with time restrictions ⋮ Dividing splittable goods evenly and with limited fragmentation ⋮ The \(k\)-partitioning problem ⋮ A new approach for bicriteria partitioning problem

Cites Work

• Lower bounds and heuristic algorithms for the \(k_i\)-partitioning problem
• The \(k\)-partitioning problem
• An approximation algorithm for the generalized assignment problem
• Approximating Scheduling Machines with Capacity Constraints
• Bounds for the cardinality constrained \(P \|C_{max}\) problem

This page was built for publication: A 3/2-approximation algorithm for \(k_i\)-partitioning