A note on graph balancing problems with restrictions

DOI10.1016/J.IPL.2009.09.015MaRDI QIDQ990093zbMATHOpenAlexFDO

Authors Kangbok Lee, Joseph Y.-T. Leung, Michael L. Pinedo

Publication date 2 September 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2009.09.015

zbMATH Keywords

computational complexityapproximation algorithmFPTAScombinatorial problemsparallel machines schedulingeligibility constraintsfully polynomial time approximation schemegraph balancing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Graph balancing: a special case of scheduling unrelated parallel machines
• Graph orientation with edge modifications
• On the most imbalanced orientation of a graph
• A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges
• A 3/2-approximation algorithm for the graph balancing problem with two weights

Cites work

• scientific article; zbMATH DE number 5345854 (Why is no real title available?)
• scientific article; zbMATH DE number 5764783 (Why is no real title available?)
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
• Approximation algorithms for scheduling unrelated parallel machines
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• Parallel machine scheduling of machine-dependent jobs with unit-length.
• Parallel machine scheduling under a grade of service provision
• Parallel machine scheduling with job assignment restrictions
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Scheduling parallel machines with inclusive processing set restrictions
• Semi-matchings for bipartite graphs and load balancing.

Cited in

(8)

• On some special cases of the restricted assignment problem
• Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments
• Graph balancing with orientation costs
• A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges
• On the configuration-LP for scheduling on unrelated machines
• A 3/2-approximation algorithm for the graph balancing problem with two weights
• Scheduling reclaimer operations in the stockyard to minimize makespan
• Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs

This page was built for publication: A note on graph balancing problems with restrictions

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