Improved Approximation Algorithms for Broadcast Scheduling

DOI10.1137/060674417MaRDI QIDQ3631906zbMATH OpenOpenAlexFDO

Authors N. Bansal, Don Coppersmith, Maxim Sviridenko

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 algorithmbroadcast schedulingLP rounding

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Algorithms for minimizing response time in broadcast scheduling
• scientific article; zbMATH DE number 2086938
• Approximating the average response time in broadcast scheduling
• scientific article; zbMATH DE number 1445348
• Better scalable algorithms for broadcast scheduling

Cited in

(27)

• Scheduling broadcasts in wireless networks
• Algorithms for minimizing response time in broadcast scheduling
• Scheduling to minimize energy and flow time in broadcast scheduling
• Improved algorithm for broadcast scheduling of minimal latency in wireless ad hoc networks
• scientific article; zbMATH DE number 1670667 (Why is no real title available?)
• Approximating the average response time in broadcast scheduling
• New models and algorithms for throughput maximization in broadcast scheduling (extended abstract)
• Broadcast scheduling, algorithms and complexity
• An online scalable algorithm for average flow time in broadcast scheduling
• On Broadcast Scheduling with Limited Energy
• Better Scalable Algorithms for Broadcast Scheduling
• Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling
• scientific article; zbMATH DE number 1982183 (Why is no real title available?)
• Circular arrangements and cyclic broadcast scheduling
• scientific article; zbMATH DE number 2086938 (Why is no real title available?)
• scientific article; zbMATH DE number 2119692 (Why is no real title available?)
• scientific article; zbMATH DE number 1445348 (Why is no real title available?)
• Better scalable algorithms for broadcast scheduling
• Nearly optimal perfectly periodic schedules
• New approximations for broadcast scheduling via variants of -point rounding
• Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach
• An online scalable algorithm for average flow time in broadcast scheduling
• Minimizing Service and Operation Costs of Periodic Scheduling
• Computing and Combinatorics
• The power of proportional fairness for nonclairvoyant polytope scheduling
• Equivalence of two linear programming relaxations for broadcast scheduling.
• Polytope scheduling with groups: unified models and optimal guarantees

This page was built for publication: Improved Approximation Algorithms for Broadcast Scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3631906)