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
N1 - Funding Information:
★ Partially supported by NSF grants CCF-0728782 and CNS-0721899. ★★ Supported mainly by a Samsung Fellowship, and partially by NSF grants CCF-0728782 and CNS-0721899. ★★★ Supported by NSF Awards CCF-0728839 and CCF-0937865, and a Google Research Award. † Research supported by REU Award supplement to CCF-0728839. ‡ Partially supported by NSF grant CNS-0721899.
PY - 2011
Y1 - 2011
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 -