Graph balancing: a special case of scheduling unrelated parallel machines
From MaRDI portal
Publication:2441586
DOI10.1007/s00453-012-9668-9zbMath1295.68214OpenAlexW2081855231MaRDI QIDQ2441586
Tomáš Ebenlendr, Marek Krčál, Jiří Sgall
Publication date: 25 March 2014
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9668-9
Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (22)
On some special cases of the restricted assignment problem ⋮ On the extension complexity of scheduling polytopes ⋮ Parameterized orientable deletion ⋮ Strong LP formulations for scheduling splittable jobs on unrelated machines ⋮ Approximation algorithms for the graph balancing problem with two speeds and two job lengths ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ Structural parameters for scheduling with assignment restrictions ⋮ Restricted assignment scheduling with resource constraints ⋮ Compact LP Relaxations for Allocation Problems ⋮ A 3/2-approximation algorithm for the graph balancing problem with two weights ⋮ Estimating the makespan of the two-valued restricted assignment problem ⋮ Unnamed Item ⋮ Scheduling reclaimer operations in the stockyard to minimize makespan ⋮ Unnamed Item ⋮ Simpler and Better Algorithms for Minimum-Norm Load Balancing ⋮ Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs ⋮ Unnamed Item ⋮ Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments ⋮ Approximate algorithms for unrelated machine scheduling to minimize makespan ⋮ Upper and lower degree-constrained graph orientation with minimum penalty ⋮ On minimizing the makespan when some jobs cannot be assigned on the same machine ⋮ Degree-constrained graph orientation: maximum satisfaction and minimum violation
Cites Work
- Unnamed Item
- 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
- Approximation algorithms for scheduling unrelated parallel machines
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- Minimizing maximum indegree
- A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
- An optimal rounding gives a better approximation for scheduling unrelated machines
- The Santa Claus problem
- GRAPH ORIENTATION TO MAXIMIZE THE MINIMUM WEIGHTED OUTDEGREE
- On the Configuration-LP for Scheduling on Unrelated Machines
- GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
- A unified approach to scheduling on unrelated parallel machines
- Santa Claus Meets Hypergraph Matchings
- Convex programming for scheduling unrelated parallel machines
- A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
- Exact and Approximate Algorithms for Scheduling Nonidentical Processors
- Santa Claus Schedules Jobs on Unrelated Machines
- On Allocating Goods to Maximize Fairness
- MaxMin allocation via degree lower-bounded arborescences
- An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods
- Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
- Improved Approximation Schemes for Scheduling Unrelated Parallel Machines
This page was built for publication: Graph balancing: a special case of scheduling unrelated parallel machines
