A 3/2-approximation algorithm for the graph balancing problem with two weights
From MaRDI portal
Publication:1736801
DOI10.3390/a9020038zbMath1461.05218OpenAlexW2412591217MaRDI QIDQ1736801
Roberto Solis-Oba, Daniel R. Page
Publication date: 26 March 2019
Published in: Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.3390/a9020038
schedulingmakespan minimizationapproximation algorithmsgraph balancing problemrestricted assignment problem
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (6)
Makespan minimization on unrelated parallel machines with a few bags ⋮ Approximation algorithms for the graph balancing problem with two speeds and two job lengths ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments ⋮ Upper and lower degree-constrained graph orientation with minimum penalty
Cites Work
- Unnamed Item
- On the configuration-LP for scheduling on unrelated machines
- Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
- Approximation algorithms for scheduling unrelated parallel machines
- A note on graph balancing problems with restrictions
- The 2-valued case of makespan minimization with assignment constraints
- A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
- Graph balancing: a special case of scheduling unrelated parallel machines
- An optimal rounding gives a better approximation for scheduling unrelated machines
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- On Representatives of Subsets
- Santa Claus Schedules Jobs on Unrelated Machines
- On (1,∊)-Restricted Assignment Makespan Minimization
- Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
This page was built for publication: A 3/2-approximation algorithm for the graph balancing problem with two weights