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

DOI10.1137/16M1099583zbMath1464.90025arXiv1511.07826MaRDI QIDQ4997316

Aravind Srinivasan, Nikhil Bansal, Ola Svensson

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

scheduling; semidefinite programming; approximation algorithms; SDP; rounding theorems

Mathematics Subject Classification ID

90C22: Semidefinite programming

90B35: Deterministic scheduling theory in operations research

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms