Scheduling broadcasts with deadlines. (English) Zbl 1071.68015
Summary: We investigate the problem of scheduling broadcasts in data delivering systems via broadcast, where a number of requests from several clients can be simultaneously satisfied by one broadcast of a server. Most of prior work has focused on minimizing the total flow time of requests. It assumes that once a request arrives, it will be held until satisfied. In this paper, we are concerned with the situation that clients may leave the system if their requests are still unsatisfied after waiting for some time, that is, each request has a deadline. The problem of maximizing the throughput, for example, the total number of satisfied requests, is developed, and there are given online algorithms achieving constant competitive ratios.
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
References:
| [1] | Aacharya, S.; Muthukrishnan, S., Scheduling on-demand broadcastsnew metrics and algorithms, (ACM/IEEE Int. Conf. on Mobile Computing and Networking (1998)), 43-54 |
| [2] | Aksoy, D.; Franklin, M., Scheduling for large scale on-demand data broadcast, (Proc. of IEEE INFOCOM (1998)), 651-659 |
| [3] | Bartal, Y.; Muthukrishnan, S., Minimizing maximum response time in scheduling broadcasts, (Proc. 11th ACM-SIAM Symp. on Discrete Algorithms (2000)), 558-559 · Zbl 0954.68503 |
| [4] | DirecPC Home Page, http://www.direcpc.com/.; DirecPC Home Page, http://www.direcpc.com/. |
| [5] | Edmonds, J.; Pruhs, K., Broadcast schedulingwhen fairness is fine, (Proc. 13th ACM-SIAM Symp. on Discrete Algorithms (2002)), 421-430 · Zbl 1254.90069 |
| [6] | Erlebach, T.; Hall, A., NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow, (Proc. 13th ACM-SIAM Symp. on Discrete Algorithms (2002)), 194-202 · Zbl 1154.90445 |
| [7] | A. Fiat, G.J. Woeginger (Eds.), Online scheduling, online algorithms: the state of the art, Lecture Notes in Computer Science, Vol. 1442, Springer, Berlin, 1998.; A. Fiat, G.J. Woeginger (Eds.), Online scheduling, online algorithms: the state of the art, Lecture Notes in Computer Science, Vol. 1442, Springer, Berlin, 1998. · Zbl 1177.68009 |
| [8] | Gandhi, R.; Khuller, S.; Kim, Y. A.; Wan, Y. C., Algorithms for minimizing response time in broadcast scheduling, (Proc. 9th Int. Integer Programming and Combinatorial Optimization (IPCO) Conf. (2002)), 425-438 · Zbl 1049.90510 |
| [9] | Jiang, S.; Vaidya, N., Scheduling data broadcasts to “impatient” users, (Proc. ACM Int. Workshop on Data Engineering for Wireless and Mobile Access (1999)), 52-59 |
| [10] | Kalyanasundaram, B.; Pruhs, K.; Velauthapillai, M., Scheduling broadcasts in wireless networks, (Proc. 8th European Symp. on Algorithms (ESA) (2000)), 290-301 · Zbl 0974.90503 |
| [11] | Kalyanasundaram, B.; Velauthapillai, M., Broadcast scheduling under deadline, (Proc. 11th European Symp. on Algorithms (ESA) (2003)), 313-324 · Zbl 1266.68072 |
| [12] | Lipton, R.; Tomkins, A., Online interval scheduling, (Proc. 5th ACM-SIAM Symp. on Discrete Algorithms (1994)), 302-311 · Zbl 0873.68012 |
| [13] | van den Akker, M.; Hoogeven, H.; Vakhania, N., Restarts can help in the on-line minimization of the maximum delivery time on a single machine, (Proc. 8th European Symp. on Algorithms (ESA) (2000)), 427-436 · Zbl 0974.68504 |
| [14] | Woeginger, G. J., On-line scheduling of jobs with fixed start and end times, Theoret. Comput. Sci., 130, 5-16 (1994) · Zbl 0810.68068 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
