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

doi:10.1007/978-3-642-18318-8_7

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Approximation and Online Algorithms - 8th International Workshop, WAOA 2010, Revised Papers
Pages	71-82
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-18318-8_7
State	Published - Feb 7 2011
Event	8th International Workshop on Approximation and Online Algorithms, WAOA 2010 - Liverpool, United Kingdom Duration: Sep 9 2010 → Sep 10 2010

Publication series

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

Other

Other	8th International Workshop on Approximation and Online Algorithms, WAOA 2010
Country	United Kingdom
City	Liverpool
Period	9/9/10 → 9/10/10

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-18318-8_7

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

Chekuri, C., Gal, A., Im, S., Khuller, S., Li, J., McCutchen, R., Moseley, B., & Raschid, L. (2011). New models and algorithms for throughput maximization in broadcast scheduling (extended abstract). In Approximation and Online Algorithms - 8th International Workshop, WAOA 2010, Revised Papers (pp. 71-82). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6534 LNCS). https://doi.org/10.1007/978-3-642-18318-8_7

Chekuri, Chandra ; Gal, Avigdor ; Im, Sungjin ; Khuller, Samir ; Li, Jian ; McCutchen, Richard ; Moseley, Benjamin ; Raschid, Louiqa. / New models and algorithms for throughput maximization in broadcast scheduling (extended abstract). Approximation and Online Algorithms - 8th International Workshop, WAOA 2010, Revised Papers. 2011. pp. 71-82 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b66a5a40121a4382a40b889e714869e6,

title = "New models and algorithms for throughput maximization in broadcast scheduling (extended abstract)",

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.",

author = "Chandra Chekuri and Avigdor Gal and Sungjin Im and Samir Khuller and Jian Li and Richard McCutchen and Benjamin Moseley and Louiqa Raschid",

year = "2011",

month = feb,

day = "7",

doi = "10.1007/978-3-642-18318-8_7",

language = "English (US)",

isbn = "9783642183171",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "71--82",

booktitle = "Approximation and Online Algorithms - 8th International Workshop, WAOA 2010, Revised Papers",

note = "8th International Workshop on Approximation and Online Algorithms, WAOA 2010 ; Conference date: 09-09-2010 Through 10-09-2010",

}

Chekuri, C, Gal, A, Im, S, Khuller, S, Li, J, McCutchen, R, Moseley, B & Raschid, L 2011, New models and algorithms for throughput maximization in broadcast scheduling (extended abstract). in Approximation and Online Algorithms - 8th International Workshop, WAOA 2010, Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6534 LNCS, pp. 71-82, 8th International Workshop on Approximation and Online Algorithms, WAOA 2010, Liverpool, United Kingdom, 9/9/10. https://doi.org/10.1007/978-3-642-18318-8_7

New models and algorithms for throughput maximization in broadcast scheduling (extended abstract). / Chekuri, Chandra; Gal, Avigdor; Im, Sungjin; Khuller, Samir; Li, Jian; McCutchen, Richard; Moseley, Benjamin; Raschid, Louiqa.

Approximation and Online Algorithms - 8th International Workshop, WAOA 2010, Revised Papers. 2011. p. 71-82 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6534 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Chekuri, Chandra

AU - Gal, Avigdor

AU - Im, Sungjin

AU - Khuller, Samir

AU - Li, Jian

AU - McCutchen, Richard

AU - Moseley, Benjamin

AU - Raschid, Louiqa

PY - 2011/2/7

Y1 - 2011/2/7

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=79551566340&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79551566340&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-18318-8_7

DO - 10.1007/978-3-642-18318-8_7

M3 - Conference contribution

AN - SCOPUS:79551566340

SN - 9783642183171

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 71

EP - 82

BT - Approximation and Online Algorithms - 8th International Workshop, WAOA 2010, Revised Papers

T2 - 8th International Workshop on Approximation and Online Algorithms, WAOA 2010

Y2 - 9 September 2010 through 10 September 2010

ER -

Chekuri C, Gal A, Im S, Khuller S, Li J, McCutchen R et al. New models and algorithms for throughput maximization in broadcast scheduling (extended abstract). In Approximation and Online Algorithms - 8th International Workshop, WAOA 2010, Revised Papers. 2011. p. 71-82. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-18318-8_7