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 -