Approximating Scheduling Machines with Capacity Constraints

DOI10.1007/978-3-642-02270-8_29zbMath1248.90054arXiv0906.3056OpenAlexW1601005720MaRDI QIDQ5321720

Gang Wang, Chi Zhang, Jing Liu, Xiaoguang Liu

Publication date: 14 July 2009

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0906.3056

zbMATH Keywords

schedulingapproximationcapacity constraintsiterative rounding

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items (2)

A 3/2-approximation algorithm for \(k_i\)-partitioning ⋮ An Efficient PTAS for Parallel Machine Scheduling with Capacity Constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• A factor 2 approximation algorithm for the generalized Steiner network problem
• An approximation algorithm for scheduling two parallel machines with capacity constraints.
• A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
• A comment on scheduling two parallel machines with capacity constraints
• Approximating minimum bounded degree spanning trees to within one of optimal
• Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling

This page was built for publication: Approximating Scheduling Machines with Capacity Constraints