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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bansal, N., Coppersmith, D., Sviridenko, M.: Improved approximation algorithms for broadcast scheduling. In: SODA, pp. 344–353 (2006)
Bartal, Y., Muthukrishnan, S.: Minimizing maximum response time inscheduling broadcasts. In: SODA, pp. 558–559 (2000)
Calinescu, G., Chekuri, C., Pal, M., Vondrak, J.: Maximizing a monotone submodular set function subject to a matroid constraint. SIAM J. on Computing (to appear)
Chan, W., Lam, T., Ting, H., Wong, P.: New Results on On-Demand Broadcasting with Deadline via Job Scheduling with Cancellation. In: Chwa, K.-Y., Munro, J.I.J. (eds.) COCOON 2004. LNCS, vol. 3106, pp. 210–218. Springer, Heidelberg (2004)
Carney, D., Lee, S., Zdonik, S.: Scalable Application-Aware Data Freshening. In: ICDE, pp. 481–492 (2003)
Chang, J., Erlebach, T., Gailis, R., Khuller, S.: Broadcast Scheduling: Algorithms and Complexity. In: SODA, pp. 473–482 (2008)
Charikar, M., Khuller, S.: A robust maximum completion time measure for scheduling. In: SODA, pp. 324–333 (2006)
Chekuri, C., Im, S., Moseley, B.: Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 444–455. Springer, Heidelberg (2009)
Chekuri, C., Vondrak, J., Zenklusen, R.: Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures. In: FOCS (2010)
Chrobak, M., Dürr, C., Jawor, W., Kowalik, L., Kurowski, M.: A Note on Scheduling Equal-Length Jobs to Maximize Throughput. J. of Scheduling 9(1), 71–73 (2006)
Deolasee, P., Katkar, A., Panchbudhe, P., Ramamritham, K., Shenoy, P.: Adaptive Push-Pull: Deisseminating Dynamic Web Data. In: WWW (2001)
Eckstein, J., Gal, A., Reiner, S.: Monitoring an Information Source under a Politeness Constraint. INFORMS Journal on Computing 20(1), 3–20 (2007)
Edmonds, J., Pruhs, K.: Multicast pull scheduling: when fairness is fine. In: SODA, pp. 421–430 (2002)
Edmonds, J., Pruhs, K.: A maiden analysis of longest wait first. In: SODA, pp. 811–820 (2004)
Gal, A., Eckstein, J.: Managing Periodically Updated Data in Relational Databases: A Stochastic Modeling Approach. JACM 48(6), 1141–1183 (2001)
Gandhi, R., Khuller, S., Kim, Y., Wan, Y.C.: Algorithms for minimizing response time in broadcast scheduling. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol. 2337, pp. 415–424. Springer, Heidelberg (2002)
Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding and its applications to approximation algorithms. JACM 53(3), 324–360 (2006); Preliminary version in FOCS (2002)
Im, S., Moseley, B.: An Online Scalable Algorithm for Average Flow Time in Broadcast Scheduling. In: SODA (2010)
Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47(4), 617–643 (2000)
Kalyanasundaram, B., Pruhs, K., Velauthapillai, M.: Scheduling broadcasts in wireless networks. In: Paterson, M. (ed.) ESA 2000. LNCS, vol. 1879, pp. 290–301. Springer, Heidelberg (2000)
Kim, J., Chwa, K.: Scheduling broadcasts with deadlines. Theor. Comput. Sci. 325, 479–488 (2004)
Motwani, R., Raghavan, P.: Randomized Algorithms. ACM Comput. Surveys 28(1), 33–37 (1996)
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)
Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions - I. Mathematical Programming 14(1), 265–294 (1978)
Pandey, S., Dhamdhere, K., Olston, C.: WIC: A General-Purpose Algorithm for Monitoring Web Information Sources. In: VLDB, pp. 360–371 (2004)
Roitman, H., Gal, A., Raschid, L.: Satisfying Complex Data Needs using Pull-Based Online Monitoring of Volatile Data Sources. In: ICDE (2008)
Roitman, H.: Profile Based Online Data Delivery - Model and Algorithms. Ph.D. Thesis (2008)
Roitman, H., Gal, A., Raschid, L.: On Trade-offs in Event Delivery Systems. In: The 4th ACM International Conference on Distributed Event-Based Systems, DEBS (2010)
Zheng, F., Fung, S., Chan, W., Chin, F., Poon, C., Wong, P.: Improved On-Line Broadcast Scheduling with Deadlines. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol. 4112, pp. 320–329. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chekuri, C. et al. (2011). New Models and Algorithms for Throughput Maximization in Broadcast Scheduling. In: Jansen, K., Solis-Oba, R. (eds) Approximation and Online Algorithms. WAOA 2010. Lecture Notes in Computer Science, vol 6534. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-18318-8_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-18318-8_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-18317-1
Online ISBN: 978-3-642-18318-8
eBook Packages: Computer ScienceComputer Science (R0)