A 3/2-approximation algorithm for the graph balancing problem with two weights

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

zbMATH Keywords

schedulingmakespan minimizationapproximation algorithmsgraph balancing problemrestricted assignment problem

Mathematics Subject Classification ID

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