Combining Online Algorithms for Acceptance and Rejection

The journal version combines 2 conference papers:

1. "Combining Online Algorithms for Rejection and Acceptance"
   Written by Yossi Azar, Avrim Blum, and Yishay Mansour. (Note that I am not an author.)
   Proceedings of 15th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 159-163, 2003.
2. "Improved combination of online algorithms for acceptance and rejection"
   Written with Yishay Mansour.
   Proceedings of 16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 265-266, 2004.

Download

• Journal version from Theory of Computing or directly as gzipped postscript or pdf
• SPAA 2004 version from ACM Digital Library: http://doi.acm.org/10.1145/1007912.1007952
• SPAA 2004 version directly from this website: gzipped postscript or pdf

Abstract (journal version):

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 requests accepted) and under cost models (e.g., with a goal of approximately minimizing the number of requests rejected). Unfortunately, algorithms designed for these two measures can often be quite different, even polar opposites. In this work we consider the problem of combining algorithms designed for each of these objectives in a way that is good under both measures simultaneously. More formally, we are given an algorithm A that is c_A-competitive with respect to the number of accepted requests and an algorithm R that is c_R-competitive with respect to the number of rejected requests. We show how to derive a combined algorithm with competitive ratio O(c_Rc_A) for rejection and O(c_A) for acceptance. We also build on known techniques to show that given a collection of k algorithms, we can construct one master algorithm that performs similarly to the best algorithm among the k for the acceptance problem and another master algorithm that performs similarly 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 that guarantees both rejection and acceptance competitiveness.

SPAA 2004 Abstract:

Given two admission control algorithms that are c_A-accept-competitive and c_R-reject-competitive respectively, we show how to create an algorithm that is simultaneously O(c_A)-accept-competitive and O(c_Ac_R)-reject-competitive. Also, the combined algorithm makes no reference to the offline optimal solution. This improves on work of Azar, Blum, and Mansour, whose combined algorithm was O(c_A²)-accept-competitive.