Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time
From MaRDI portal
Publication:5236279
DOI10.1137/1.9781611975482.95zbMath1431.68154MaRDI QIDQ5236279
Shi Li, Janardhan Kulkarni, Shashwat Garg
Publication date: 15 October 2019
Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/1.9781611975482.95
68W40: Analysis of algorithms
90B35: Deterministic scheduling theory in operations research
68W25: Approximation algorithms
Related Items
An improved approximation algorithm for scheduling under arborescence precedence constraints, $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm