Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
Publication:4997316
DOI10.1137/16M1099583zbMath1464.90025arXiv1511.07826OpenAlexW2269281743WikidataQ126978895 ScholiaQ126978895MaRDI QIDQ4997316
Aravind Srinivasan, Ola Svensson, Nikhil Bansal
Publication date: 29 June 2021
Published in: SIAM Journal on Computing, Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1511.07826
Semidefinite programming (90C22) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for scheduling unrelated parallel machines
- On the stochastic independence properties of hard-core distributions
- Minimizing average completion time in the presence of release dates
- A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines
- A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- Approximation Techniques for Average Completion Time Scheduling
- Single Machine Scheduling with Release Dates
- A PTAS for minimizing the weighted sum of job completion times on parallel machines
- The Santa Claus problem
- Santa claus meets hypergraph matchings
- Convex quadratic and semidefinite programming relaxations in scheduling
- A unified approach to scheduling on unrelated parallel machines
- Dependent rounding and its applications to approximation algorithms
- Convex programming for scheduling unrelated parallel machines
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- Task Scheduling in Networks
- Solving Optimization Problems with Diseconomies of Scale via Decoupling
- Scheduling Unrelated Machines by Randomized Rounding
- Santa Claus Schedules Jobs on Unrelated Machines
- Approximating the Configuration-LP for Minimizing Weighted Sum of Completion Times on Unrelated Machines
- On Allocating Goods to Maximize Fairness