A note on graph balancing problems with restrictions
DOI10.1016/J.IPL.2009.09.015zbMATH Open1197.05147OpenAlexW2066813640MaRDI QIDQ990093FDOQ990093
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
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
computational complexityapproximation algorithmFPTAScombinatorial problemsparallel machines schedulingeligibility constraintsfully polynomial time approximation schemegraph balancing
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Approximation algorithms for scheduling unrelated parallel machines
- Title not available (Why is that?)
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- Parallel machine scheduling with job assignment restrictions
- Parallel machine scheduling under a grade of service provision
- Scheduling parallel machines with inclusive processing set restrictions
- An optimal rounding gives a better approximation for scheduling unrelated machines
- Parallel machine scheduling of machine-dependent jobs with unit-length.
- Title not available (Why is that?)
- Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
- Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
- Semi-matchings for bipartite graphs and load balancing.
Cited In (8)
- On some special cases of the restricted assignment problem
- A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges
- A 3/2-approximation algorithm for the graph balancing problem with two weights
- Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments
- Scheduling reclaimer operations in the stockyard to minimize makespan
- Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs
- Structural parameters for scheduling with assignment restrictions
- On the configuration-LP for scheduling on unrelated machines
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)
