Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach
From MaRDI portal
Publication:5383964
DOI10.1137/1.9781611973402.5zbMath1422.68288OpenAlexW4255357113MaRDI QIDQ5383964
Ravishankar Krishnaswamy, Shi Li, Nikhil Bansal, Moses Charikar
Publication date: 20 June 2019
Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/9a60b0b57df5ff537e58a85c6648f1b3767f1887
Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Approximation-Friendly Discrepancy Rounding, Minimizing the maximum flow time in batch scheduling, An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound, Better Bin Packing Approximations via Discrepancy Theory, The online food delivery problem on stars