Improved Approximation Algorithms for Broadcast Scheduling

DOI10.1137/060674417zbMath1187.68704MaRDI QIDQ3631906

Don Coppersmith, M. I. Sviridenko, Nikhil Bansal

Publication date: 22 June 2009

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://research.tue.nl/nl/publications/f3d77fe3-31cc-4b43-aac1-d940c9b06e21

zbMATH Keywords

approximation algorithm; LP rounding; broadcast scheduling

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

90B35: Deterministic scheduling theory in operations research

90C59: Approximation methods and heuristics in mathematical programming

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

68W25: Approximation algorithms