Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach

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

Mathematics Subject Classification ID

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