Combining online algorithms for rejection and acceptance

ABSTRACT

Resource allocation and admission control are critical tasks in a communication network, that often must be performed online. Algorithms for these types of problems have been considered both under benefit models (e.g., with a goal of approximately maximizing the number of calls accepted) and under cost models (e.g., with a goal of approximately minimizing the number of calls rejected). Unfortunately, algorithms designed for these two measures can often be quite different, even polar opposites (e.g., [1, 8]). In this work we consider the problem of combining algorithms designed for each of these objectives in a way that simultaneously is good under both measures. More formally, we are given an algorithm A which is cA competitive w.r.t. the number of accepted calls and an algorithm R which is cR competitive w.r.t. the number of rejected calls. We derive a combined algorithm whose competitive ratio is O(cR cA) for rejection and O(cA²) for acceptance. We also show building on known techniques that given a collection of k algorithms, we can construct one master algorithm which performs similar to the best algorithm among the k for the acceptance problem and another master algorithm which performs similar to the best algorithm among the k for the rejection problem. Using our main result we can combine the two master algorithms to a single algorithm which guarantees both rejection and acceptance competitiveness.

REFERENCES

• 1: Ran Adler , Yossi Azar, Beating the logarithmic lower bound: randomized preemptive disjoint paths and call control algorithms, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.1-10, January 17-19, 1999, Baltimore, Maryland, United States
• 2: Baruch Awerbuch , Yossi Azar , Amos Fiat , Tom Leighton, Making commitments in the face of uncertainty: how to pick a winner almost every time (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.519-530, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238000]
• 3: B. Awerbuch, Y. Azar, and S. Plotkin. Throughput-competitive online routing. In 34th IEEE Symposium on Foundations of Computer Science, pages 32--40, 1993.
• 4: Baruch Awerbuch , Yair Bartal , Amos Fiat , Adi Rosén, Competitive non-preemptive call control, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.312-320, January 23-25, 1994, Arlington, Virginia, United States
• 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 Found. of Comp. Science, pages 412--423, 1994.
• 6: Yossi Azar , Andrei Z. Broder , Mark S. Manasse, On-line choice of on-line algorithms, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.432-440, January 25-27, 1993, Austin, Texas, United States
• 7: Ricardo A. Baeza-Yates , Joseph C. Culberson , Gregory J. E. Rawlins, Searching in the plane, Information and Computation, v.106 n.2, p.234-252, Oct. 1993 [doi>10.1006/inco.1993.1054]
• 8: Avrim Blum , Adam Kalai , Jon M. Kleinberg, Admission Control to Minimize Rejections, Proceedings of the 7th International Workshop on Algorithms and Data Structures, p.155-164, August 08-10, 2001
• 9: Amos Fiat , Dean P. Foster , Howard Karloff , Yuval Rabani , Yiftach Ravid , Sundar Vishwanathan, Competitive algorithms for layered graph traversal, Proceedings of the 32nd annual symposium on Foundations of computer science, p.288-297, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185381]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
QoS, admission control, competitive, on-line