New models and algorithms for throughput maximization in broadcast scheduling (extended abstract)

Chandra Chekuri*, Avigdor Gal, Sungjin Im, Samir Khuller, Jian Li, Richard McCutchen, Benjamin Moseley, Louiqa Raschid

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

In this paper we consider some basic scheduling questions motivated by query processing that involve accessing resources (such as sensors) to gather data. Clients issue requests for data from resources and the data may be dynamic or changing which imposes temporal constraints on the delivery of the data. A proxy server has to compute a probing schedule for the resources since it can probe a limited number of resources at each time step. Due to overlapping client requests, multiple queries can be answered by probing the resource at a certain time. This leads to problems related to some well-studied broadcast scheduling problems. However, the specific requirements of the applications motivate some generalizations and variants of previously studied metrics for broadcast scheduling. We consider both online and offline versions of these problems and provide new algorithms and results.

Original languageEnglish (US)
Title of host publicationApproximation and Online Algorithms - 8th International Workshop, WAOA 2010, Revised Papers
Pages71-82
Number of pages12
DOIs
StatePublished - 2011
Event8th International Workshop on Approximation and Online Algorithms, WAOA 2010 - Liverpool, United Kingdom
Duration: Sep 9 2010Sep 10 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6534 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other8th International Workshop on Approximation and Online Algorithms, WAOA 2010
Country/TerritoryUnited Kingdom
CityLiverpool
Period9/9/109/10/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'New models and algorithms for throughput maximization in broadcast scheduling (extended abstract)'. Together they form a unique fingerprint.

Cite this