Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines

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

zbMATH Keywords

schedulingsemidefinite programmingapproximation algorithmsSDProunding theorems

Mathematics Subject Classification ID

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

Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints, Parallel-machine scheduling of jobs with mixed job-, machine- and position-dependent processing times, Integrality gaps for colorful matchings, Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines, Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations, Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling, Semidefinite and linear programming integrality gaps for scheduling identical machines, A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies, Contention resolution, matrix scaling and fair allocation, Performance guarantees of local search for minsum scheduling problems

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