Volume 1 (2005)
Article 6 pp. 105-117
Combining Online Algorithms for Acceptance and Rejection
Received: January 21, 2005
Published: September 14, 2005
Published: September 14, 2005
Keywords: Algorithms, communication networks, resource allocation, online algorithms, competitive analysis, Quality of Service, admission control
ACM Classification: F.2.2, C.2.2
AMS Classification: 68W05
Abstract: [Plain Text 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
cA competitive with respect to the number
of accepted requests and an algorithm R that is
cR competitive with respect to the number
of rejected requests. We show how to derive a combined algorithm
with competitive ratio O(cRcA) for rejection
and O(cA) 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.

Licensed under a Creative Commons License