A 3/2-approximation algorithm for k_i-partitioning

DOI10.1016/J.ORL.2011.06.005MaRDI QIDQ408403zbMATH OpenOpenAlexFDO

Authors Hans Kellerer, V. M. Kotov

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

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

Recommendations

• The \(k\)-partitioning problem
• \(k\)-partitioning problems with partition matroid constraint
• Fast exact and approximate algorithms for k-partition and scheduling independent tasks
• An approximation algorithm for scheduling on three dedicated machines
• Approximation algorithms for \(k\)-partitioning problems with partition matroid constraint

Cites work

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

Cited in

(15)

• Approximation algorithms for \(k\)-partitioning problems with partition matroid constraint
• A tight bound for 3-partitioning
• A new approach for bicriteria partitioning problem
• A Bi-Criteria FPTAS for Scheduling with Memory Constraints on Graphs with Bounded Tree-Width
• Online cardinality constrained scheduling
• Lower bounds and heuristic algorithms for the \(k_i\)-partitioning problem
• Three Partition Refinement Algorithms
• A 7/6–Approximation Algorithm For 3-Partitioning And Its Application To Multiprocessor Scheduling
• The \(k\)-partitioning problem
• Domination analysis for minimum multiprocessor scheduling
• An efficient PTAS for parallel machine scheduling with capacity constraints
• Three-partitioning containing kernels: Complexity and heuristic
• Dividing splittable goods evenly and with limited fragmentation
• EPTAS for parallel identical machine scheduling with time restrictions
• Operations research models for coalition structure in collaborative logistics

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

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