Combining Online Algorithms for Acceptance and Rejection

by Yossi Azar, Avrim Blum, David P. Bunde, and Yishay Mansour

Theory of Computing, Volume 1(6), pp. 105-117, 2005

Bibliography with links to cited articles

[1]    R. Adler and Y. Azar: Beating the logarithmic lower bound: randomized preemptive disjoint paths and call control algorithms. J. of Scheduling, pp. 113–129, 2003. Prelimary version in Proc. 10th ACM-SIAM Symp. on Discrete Algorithms, pp. 1–10, 1999. [doi:10.1023/A:1022933824889, SODA:314500.314512, JSched:jq27641706456655].

[2]   B. Awerbuch, Y. Azar, A. Fiat, and T. Leighton: Making commitments in the face of uncertainty: How to pick a winner almost every time. In Proc. 28th ACM Symp. on Theory of Computing, pp. 519–530, 1996. [STOC:237814.238000].

[3]   B. Awerbuch, Y. Azar, and S. Plotkin: Throughput-competitive online routing. In Proc. 34th IEEE Symp. on Foundations of Computer Science, pp. 32–40, 1993. [FOCS:10.1109/SFCS.1993.366884].

[4]   B. Awerbuch, Y. Bartal, A. Fiat, and A. RosÚn: Competitive non-preemptive call control. In Proc. 5th ACM-SIAM Symp. on Discrete Algorithms, pp. 312–320, 1994. [SODA:314464.314510].

[5]   B. Awerbuch, R. Gawlick, T. Leighton, and Y. Rabani: On-line admission control and circuit routing for high performance computation and communication. In Proc. 35th IEEE Symp. on Foundations of Computer Science, pp. 412–423, 1994. [FOCS:10.1109/SFCS.1994.365675].

[6]   Y. Azar, A. Blum, and Y. Mansour: Combining online algorithms for rejection and acceptance. In Proc. 15th ACM Symp. Parallelism in Algorithms and Architectures, pp. 159–163, 2003. [SPAA:10.1145/777412.777438].

[7]   Y. Azar, A. Broder, and M. Manasse: On-line choice of on-line algorithms. In Proc. 4th ACM-SIAM Symp. on Discrete Algorithms, pp. 432–440, 1993. [SODA:313559.313847].

[8]   R. Baeza-Yates, J. Culberson, and G. Rawlins: Searching in the plane. Information and Computation, 106(2):234–252, 1993. Preliminary version in Proc. 1st Scandinavian Workshop on Algorithm Theory, LNCS 318, pp. 176–189, 1988. [IandC:10.1006/inco.1993.1054].

[9]   A. Blum, A. Kalai, and J. Kleinberg: Admission control to minimize rejections. Internet Mathematics, 1(2):165–176, 2004. Preliminary version in Proc. 7th Workshop on Algorithms and Data Structures, LNCS 2125, pp. 155–164, 2001. [WADS:9ukehq56d6yp2m22, InternetMath:1(2):165–176].

[10]   D.P. Bunde and Y. Mansour: Improved combination of online algorithms for acceptance and rejection. In Proc. 16th ACM Symp. Parallelism in Algorithms and Architectures, pp. 265–266, 2004. [SPAA:10.1145/1007912.1007952].

[11]   A. Fiat, D. Foster, H. Karloff, Y. Rabani, Y. Ravid, and S. Vishwanathan: Competitive algorithms for layered graph traversal. SIAM J. on Computing, 28(2):447–462, 1998. Preliminary version in Proc. 32nd IEEE Symp. on Foundations of Computer Science, pp 288–297, 1991. [FOCS:10.1109/SFCS.1991.185381, SICOMP:10.1137/S0097539795279943].