On the configuration-LP for scheduling on unrelated machines
From MaRDI portal
Publication:490331
DOI10.1007/S10951-013-0359-4zbMATH Open1305.68046OpenAlexW1605794186MaRDI QIDQ490331FDOQ490331
Authors: José Verschae, Andreas Wiese 
Publication date: 22 January 2015
Published in: Journal of Scheduling (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10951-013-0359-4
Recommendations
- On the Configuration-LP for Scheduling on Unrelated Machines
- On the configuration-LP of the restricted assignment problem
- Strong LP formulations for scheduling splittable jobs on unrelated machines
- Graph balancing: a special case of scheduling unrelated parallel machines
- Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines
Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)
Cites Work
- Exact and Approximate Algorithms for Scheduling Nonidentical Processors
- Approximation algorithms for scheduling unrelated parallel machines
- On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
- The Santa Claus problem
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- Title not available (Why is that?)
- On allocating goods to maximize fairness
- MaxMin allocation via degree lower-bounded arborescences
- An optimal rounding gives a better approximation for scheduling unrelated machines
- The power of preemption on unrelated machines and applications to scheduling orders
- Santa Claus Meets Hypergraph Matchings
- Parallel machine scheduling of machine-dependent jobs with unit-length.
- A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
- On the Configuration-LP for Scheduling on Unrelated Machines
- Santa claus meets hypergraph matchings
- Title not available (Why is that?)
- An approximation algorithm for max-min fair allocation of indivisible goods
- New constructive aspects of the Lovász local lemma
- A note on graph balancing problems with restrictions
Cited In (21)
- A 3/2-approximation algorithm for the graph balancing problem with two weights
- Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
- Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments
- Compact LP relaxations for allocation problems
- Graph balancing with orientation costs
- On the Configuration-LP for Scheduling on Unrelated Machines
- On the configuration-LP of the restricted assignment problem
- Optimal matroid partitioning problems
- Optimal matroid partitioning problems
- Parameterized orientable deletion
- Parameterized orientable deletion
- Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines
- Strong LP formulations for scheduling splittable jobs on unrelated machines
- Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs
- Semidefinite and linear programming integrality gaps for scheduling identical machines
- Approximation algorithms for the graph balancing problem with two speeds and two job lengths
- Better trees for Santa Claus
- Semidefinite and linear programming integrality gaps for scheduling identical machines
- Approximating the configuration-LP for minimizing weighted sum of completion times on unrelated machines
- Local search breaks 1.75 for graph balancing
- On minimizing the makespan when some jobs cannot be assigned on the same machine
This page was built for publication: On the configuration-LP for scheduling on unrelated machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490331)
