Minimizing maximum response time in scheduling broadcasts

Yair Bartal, Shan Muthukrishnan

Research output: Contribution to conferencePaper

50 Scopus citations


We study novel scheduling problems that arise when a data server broadcasts data items requested by users. Two or more users may have pending requests for the same data item at any given time - such `common' requests may be satisfied by broadcasting that data once. Hence, in contrast to the classical scheduling scenario, the scheduling problems arising in the broadcast case have the property that the work done for one job may satisfy some of the others. We formulate the broadcast data delivery model and the scheduling problems that arise. We present polynomial time, near-optimal, offline algorithms as well as tight bounds on the competitive ratio of the online algorithms for the basic problem of minimizing the maximum response time of a request.

Original languageEnglish (US)
Number of pages2
StatePublished - Jan 1 2000
Externally publishedYes
Event11th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA
Duration: Jan 9 2000Jan 11 2000


Other11th Annual ACM-SIAM Symposium on Discrete Algorithms
CitySan Francisco, CA, USA

All Science Journal Classification (ASJC) codes

  • Chemical Health and Safety
  • Software
  • Safety, Risk, Reliability and Quality
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Minimizing maximum response time in scheduling broadcasts'. Together they form a unique fingerprint.

Cite this