Authors Yossi Azar, Avrim Blum, David P. Bunde, Yishay Mansour,
License CC-BY-ND-2.0
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 105–117
http://theoryofcomputing.org
Combining Online Algorithms for
Acceptance and Rejection
Yossi Azar∗ Avrim Blum† David P. Bunde‡ Yishay Mansour§
Received: January 21, 2005; published: September 14, 2005.
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 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(cR cA ) for rejection and O(cA ) for acceptance.
We also build on known techniques to show that given a collection of k algorithms, we can
∗ Research supported in part by the Israel Science Foundation and by the IST Program of the EU.
† Research supported in part by NSF grants CCR-0105488, CCR-0122581, ITR IIS-0121678 and by a BSF grant.
‡ Research supported in part by NSF grant CCR-0093348.
§ Research supported in part by the Israel Science Foundation (grant No. 1079/04) and by a BSF grant.
ACM Classification: F.2.2, C.2.2
AMS Classification: 68W05
Key words and phrases: Algorithms, communication networks, resource allocation, online algorithms,
competitive analysis, Quality of Service, admission control
Authors retain copyright to their work and grant Theory of Computing unlimited rights
to publish the work electronically and in hard copy. Use of the work is permitted as
long as the author(s) and the journal are properly acknowledged. For the detailed
copyright statement, see http://theoryofcomputing.org/copyright.html.
c 2005 Yossi Azar, Avrim Blum, David P. Bunde, and Yishay Mansour DOI: 10.4086/toc.2005.v001a006
Y. A ZAR , A. B LUM , D.P. B UNDE , Y. M ANSOUR
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.
1 Introduction
Resource allocation is one of the most critical tasks in communication networks. Many network re-
sources are in constant “short supply”: this includes bandwidth (of the various links), queuing delays
(or rather the lack of queuing delays in the switches), the ability to route with bounded jitter, and many
more. If one would like to guarantee Quality of Service (QoS), one needs to allocate resources to the
requesting calls, and since those resources are bounded, it implies that requests must be rejected due to
the lack of sufficient resources in certain cases. A simple example is bandwidth allocation. Suppose we
have a link with a given capacity, and different calls request bandwidth allocation on that link. Since the
system cannot allocate more than the link capacity, it may be forced to reject some of the requests.
The resource allocation (or admission control) decision must typically be done online. That is, the
algorithm has to decide for each request whether or not to accept that request (and grant it the resources)
while having minimal (or no) knowledge of future requests. This leads very naturally to the setting
of online algorithms and using competitive analysis to evaluate performance. In fact, a wide range of
resource allocation problems have been considered in this general online setting, including call control,
admission control, active queue management, and switch throughput.
When one applies competitive analysis, one needs to decide what performance measure to focus on.
One can try either to minimize the number of rejected requests or alternatively to maximize the number
of accepted requests. We say that an algorithm is c-reject-competitive if it rejects at most c times the
number of requests rejected by the optimal algorithm OPT and c-accept-competitive if it accepts at least
1/c times as many requests as OPT . Even though OPT simultaneously both maximizes the number
of accepted requests and minimizes the number of rejected requests, it is a well known phenomena
in approximation and online algorithms that approximation ratios are not preserved when considering
the two complementary problems. In the literature the minimization version is referred to as a cost
problem and the maximization version is referred to as a benefit problem. There might be one algorithm
A that achieves a good ratio for maximizing benefit but has a poor ratio in terms of cost, and a different
algorithm R that has a good ratio for minimizing cost but a poor ratio in terms of benefit. For example,
consider a 2-accept-competitive algorithm A and a 2-reject-competitive algorithm R. If the optimal
solution OPT accepts 98% of the input, algorithm R accepts at least 96%, but algorithm A may accept
only 49%. However, if OPT accepts 50% of the input, algorithm A accepts at least 25%, but algorithm
R may accept nothing.
In the offline setting, the fact that we have two different algorithms, one for each measure, is not
really a problem: given any problem instance, we can always simulate both algorithms and take the best
solution found, which will be good under both measures simultaneously. However, in the online setting,
it is not so clear how to achieve simultaneous guarantees because we need to make the accept/reject
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 105–117 106
C OMBINING O NLINE A LGORITHMS FOR ACCEPTANCE AND R EJECTION
decisions as we go.
In this paper, we describe a procedure that given algorithms A and R that are cA -accept-competitive
and cR -reject-competitive respectively, derives a combined algorithm that is simultaneously good under
both measures. Specifically, the combined algorithm is simultaneously O(cA )-accept-competitive and
O(cR cA )-reject-competitive.1 The combined algorithm uses preemption — the ability to later reject
a request that had previously been accepted (preempted requests are regarded as rejected) — which
is known to be necessary to achieve any nontrivial guarantee in the rejection measure. At the high
level, the procedure uses the following simple intuitive notion: On the one hand, if OPT rejects only
a small fraction of the requests, the reject-competitiveness of algorithm R guarantees that it accepts a
large fraction of requests and thus it is accept-competitive as well. On the other hand, if OPT rejects
many requests, being reject-competitive is trivial (even rejecting all requests is fine), so algorithm A is
competitive by both measures. Thus, by internally simulating both algorithms, and switching between
them at just the right time, we might hope to perform well in both measures. The difficulty is showing
that requests rejected by one algorithm do not adversely affect the competitive ratio of the other. Our
algorithm does not use randomness to make its decisions, so the combined algorithm is deterministic
unless one of the input algorithms is randomized.
In fact, we give two different combining algorithms. Both achieve O(cA )-accept-competitiveness
and O(cA cR )-reject-competitiveness, but the first needs to be given the value of cA in advance, while the
second does not (neither needs to know cR ). There is an added benefit to designing an algorithm that
does not need to use the values of the competitive ratios; the ratios achieved by our second algorithm
depend only on the behavior of A and R on the specific input sequence. For example, if algorithms A and
R have log-factor competitive ratios, but happen to be constant-competitive on the actual input sequence,
then the combined algorithm is constant-competitive overall (for that input sequence).
In addition to our main result, we show how to apply known techniques to combine several admission
control algorithms so that the result performs nearly as well (according to either the cost or benefit
measure) on any given input sequence as the best of them. More specifically, given k algorithms, we
can construct a combined randomized preemptive algorithm that is O(log k)-reject-competitive to the
best algorithm among the k using techniques of Baeza-Yates et al. [8], Fiat et al. [11], and Azar et
al. [7]. Alternately, we can construct a combined randomized preemptive algorithm that is O(log k)-
accept-competitive to the best algorithm among the k using techniques of Awerbuch et al. [2]. These
two combined algorithms can be combined to one master algorithm using our main result to guarantee
both rejection and acceptance competitiveness.
1.1 Applications of the main result
Our main result can be applied to several problems. One, which motivated this work, is admission
control and call control on the line graph. Requests are intervals on the line and each edge in the graph
has a capacity, which is the maximum number of accepted requests that can use that edge. Adler and
Azar [1] give a constant accept-competitive algorithm for the problem and Blum et al. [9] give a constant
1 This paper is based on conference papers by Azar et al. [6] and Bunde and Mansour [10]. The first of these had a worse
O(c2A ) guarantee on accept-competitiveness and furthermore needed to be given cA and cR in advance, as well as the ability
to compute OPT over the requests seen in the past. The second paper improved the accept-competitive ratio to O(cA ) and
removed the need to compute OPT or to know cA or cR .
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 105–117 107
Y. A ZAR , A. B LUM , D.P. B UNDE , Y. M ANSOUR
reject-competitive algorithm for the same problem. We conclude that there is a combined algorithm that
is simultaneously constant competitive for both measures. What is interesting here is that the algorithms
are almost polar opposites. For example, if the capacity of each edge is 2, and three requests share an
edge, the algorithm of Blum et al. [9] rejects the two “outside” requests (the one that extends farthest to
the left and the one that extends farthest to the right) but the algorithm of Adler and Azar [1] rejects the
one in the middle.
Our result can also be applied when the graph is a tree and accepted requests must be disjoint.
Awerbuch et al. [4] and Awerbuch et al. [5] give O(log d)-competitive randomized (non-preemptive)
algorithms for maximizing the number of accepted requests when d is the diameter of the tree. Blum et
al. [9] shows a constant competitive algorithm for the number of rejected requests in this case. By com-
bining these two, we get an algorithm that is simultaneously O(log d)-accept-competitive and O(log d)-
reject-competitive.
Another application is the admission control problem on general graphs where each edge is of log-
arithmic capacity and each request is for a fixed path. Awerbuch et al. [3] provide an O(log n)-accept-
competitive non-preemptive algorithm and Blum et al. [9] provide an O(log n)-reject-competitive (pre-
emptive) algorithm. We conclude there are algorithms simultaneously O(log n)-accept-competitive and
O(log2 n)-reject-competitive.
We should remark that for many natural online problems it is impossible to achieve competitiveness
in the rejection measure and hence in both measures. For example, if the online algorithm can be forced
to reject a request while the offline might have not rejected any requests, then the algorithm has an
unbounded competitive ratio.
2 Model
We assume an abstract model where one request arrives at every time unit. Either the request is served
(with benefit one and cost zero), or the request is rejected (with benefit zero and cost one). A request can
also be preempted, in which case its benefit is set to zero and its cost is set to one. In this abstract model,
the only assumption we make about the resource constraints (which are what prevent us from accepting
every request) is monotonicity: if F is a feasible set of requests, then any subset of F is feasible as well.
Given a sequence σ and algorithm ALG, let BENEFITALG (σ ) be the number of requests served by ALG
and COSTALG (σ ) be the number of requests rejected by ALG. By definition, the sum of benefit and cost
is always the number of time steps, i.e. BENEFITALG (σ ) + COSTALG (σ ) = |σ | for all algorithms ALG.
An optimal algorithm OPT can either maximize the benefit BENEFITOPT (σ ) or minimize the cost
COST OPT (σ ). Note that for any input sequence, the optimal schedule is identical for both maximizing
benefit and minimizing cost.
We are given two algorithms. The first is a possibly randomized preemptive algorithm A that guar-
antees a competitive ratio of cA ≥ 1 for benefit. That is, for any sequence σ
1
E BENEFITA (σ ) ≥ BENEFITOPT (σ ) .
cA
In addition, we are given a possibly randomized preemptive algorithm R that has a guarantee of
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 105–117 108
C OMBINING O NLINE A LGORITHMS FOR ACCEPTANCE AND R EJECTION
cR ≥ 1 for cost. That is, for any sequence σ
E COSTR (σ ) ≤ cR COSTOPT (σ ) .
Notation: Given an input sequence σ , denote by σt the requests arriving by time t. As a convention,
the first request is number 1.
3 Algorithm S2
Now we describe S2, our first combining algorithm.2 Internally, S2 simulates algorithms A and R on the
input σt . That is, S2 keeps track of what requests would have been accepted or rejected had it followed
algorithm A from the start, and which would have been accepted or rejected had it followed algorithm
R from the start. If either algorithm is randomized, then the simulation is just of a single execution (not
an average over multiple runs), and our definition of quantities such as COSTR (σ ) (e.g., Lemma 3.1 and
Lemma 3.2 below) are with respect to the execution observed. At any time, S2 is in either an A phase or
an R phase. We call the algorithm corresponding to the current phase the phase algorithm. Algorithm
S2 accepts, rejects, and preempts requests in exactly the same way as the phase algorithm. Algorithm
S2 is in an R phase if COSTR (σt )/t ≤ τ, where τ = 1/(8cA ), and in an A phase otherwise. Whenever S2
switches phases, it preempts any accepted requests that the new phase algorithm did not accept. Thus,
the requests accepted by S2 are feasible since they are a subset of the requests accepted by the phase
algorithm.
3.1 Analysis of rejections
We define requests rejected because of algorithm A to be the requests rejected or preempted during an
A phase (including those rejected when switching to an A phase) and denote their number at time t with
RA (σt ). Thus, COSTS2 (σt ) ≤ RA (σt ) + COSTR (σt ).
Lemma 3.1. At any time t, RA (σt ) < COSTR (σt )/τ.
Proof. If S2 is in an A phase at time t, COSTR (σt ) > τt. Since algorithm A cannot reject more than t
requests, RA (σt ) ≤ t < COSTR (σt )/τ.
Now consider the case that S2 is in an R phase at time t. Let T be the last time when S2 was in an
A phase. By the reasoning above, RA (σT ) < COSTR (σT )/τ. Since S2 has been in an R phase since time
T + 1, RA (σt ) = RA (σT ). Also, since the number of rejections of R is a non-decreasing function of time,
COST R (σT ) ≤ COST R (σt ). Thus, RA (σt ) < COST R (σt )/τ.
Since COSTS2 (σt ) ≤ RA (σt ) + COSTR (σt ), Lemma 3.1 implies that
S2
COST (σt ) ≤ (1 + 1/τ)COSTR (σt ) .
2 We call the algorithm S2 because it is based on and improves over a previous algorithm “SWITCH” [6].
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 105–117 109
Y. A ZAR , A. B LUM , D.P. B UNDE , Y. M ANSOUR
Note that if algorithm R is randomized, then the above holds for the specific execution simulated by
algorithm S2. Now, using the fact that algorithm R is cR -reject-competitive, we can bound the reject-
competitive ratio of S2 by
E COSTS2 (σt ) 1 + τ1 E COSTR (σt )
1
≤ ≤ 1 + cR = O(cA cR ) .
COST OPT (σt ) COST OPT (σt ) τ
3.2 Analysis of acceptances
We define requests rejected because of algorithm R to be the requests rejected or preempted during an
R phase and denote their number at time t with RR (σt ).
Lemma 3.2. At any time t, RR (σt ) ≤ BENEFITOPT (σt )/(7cA ).
Proof. If time t is during an R phase, the lemma follows from
OPT
BENEFIT (σt ) ≥ BENEFITR (σt ) ≥ (1 − τ)t ≥ 7t/8
and RR (σt ) ≤ COSTR (σt ) ≤ τt = t/(8cA ).
Consider time t in an A phase. If S2 has not had an R phase, RR (σt ) = 0 so the lemma holds.
Otherwise, let t 0 be the time at which the latest R phase ended. By the argument above,
RR (σt 0 ) ≤ BENEFITOPT (σt 0 )/(7cA ) .
Since S2 was in an A phase since time t 0 ,
RR (σt ) = RR (σt 0 ) ≤ BENEFITOPT (σt 0 )/(7cA ) .
Since optimal benefit is non-decreasing with the input length, RR (σt ) ≤ BENEFITOPT (σt )/(7cA ).
Now we can prove that S2 is O(cA )-accept-competitive. We do this by bounding the number of
requests accepted by both algorithms, which is a lower bound on
the number of requests accepted by S2.
Since algorithm A is cA -accept-competitive, E BENEFITA (σ ) ≥ BENEFITOPT (σ )/cA . By Lemma 3.2,
algorithm R causes RR (σt ) ≤ BENEFITOPT (σ )/(7cA ) additional rejections. Thus,
E BENEFITS2 (σ ) ≥ BENEFITOPT (σ )/cA − BENEFITOPT (σ )/(7cA ) = (6/(7cA ))BENEFITOPT (σ )
and the accept-competitive ratio of S2 is at most (7/6)cA = O(cA ).
4 Algorithm RO
Now we define RO, our second combining algorithm.3 One problem with our previous algorithm S2
is that, while simple, it required knowing cA in advance. Algorithm RO is a bit more complicated but
3 We call this algorithm RO for Ratio Oblivious because it does not need to know the competitive ratios of the input
algorithms.
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 105–117 110
C OMBINING O NLINE A LGORITHMS FOR ACCEPTANCE AND R EJECTION
does not need to be given either of the competitive ratios as input. Internally, algorithm RO keeps times
tA and tR , plus input prefixes σA and σR of these lengths. It maintains simulations of algorithms A and
R on inputs σA and σR respectively. Whenever either of these algorithms decides to reject a request,
that request is marked. Times tA and tR advance in phases, pausing and resuming the simulations as
necessary so that max{tA ,tR } = t at time t. Specifically, phase k ≥ 0 has an R subphase, during which
time tR advances until COSTR (σR ) = 4k , followed by an A subphase, during which time tA advances
until BENEFITA (σA ) = 8 · 4k (note that a subphase may correspond to an empty set of requests). When
a new request arrives, RO accepts it if the resulting set of accepted requests is feasible. While the
resulting set is not feasible, RO preempts an arbitrary marked request (some such request must exist
since max{tA ,tR } = t). The idea of using marks to delay rejections as long as possible is called lazy
rejection.
4.1 Analysis of rejections
To analyze rejections, we first show that the algorithm maintains the invariant that BENEFITA (σA ) ≤
32COSTR (σR ). (If either A or R is randomized, then this statement is with respect to the specific execution
of each algorithm performed by RO.) During the first R subphase, the inequality holds vacuously because
BENEFITA (σA ) = 0. During the first A subphase, COST R (σR ) = 1 and BENEFITA (σA ) ≤ 8. Finally, during
phases after the first, COSTR (σR ) ≥ 4k−1 and BENEFITA (σA ) ≤ 8 · 4k .
Using the above inequality, we can bound COSTA (σA ) from above by
A OPT
COST (σA ) ≤ tA = (σA ) + BENEFITOPT (σA )
COST
≤ COSTOPT (σA ) + cA E BENEFITA (σA )
≤ COSTOPT (σA ) + 32cA E COSTR (σR ) .
Thus, the rejection competitive ratio of RO is at most
E COSTA (σA ) + COSTR (σR ) 32cA E COSTR (σR )
≤ 1+ + cR = O(cA cR ) .
COST OPT (σt ) COST OPT (σt )
4.2 Analysis of acceptances
To show that algorithm RO is O(cA )-accept-competitive, we show
RO
BENEFIT (σt ) ≥ (1/2)BENEFITA (σt )
for all times t, all inputs, and all sequences of random bits. The desired result then follows from the
competitiveness of algorithm A.
Since RO does not reject any requests during the first R subphase, it is optimal and BENEFITRO (σt ) =
BENEFITA (σt ). The first A subphase begins when algorithm R rejects (or preempts) a request C. Algo-
rithm RO accepts the same requests as algorithm A except possibly for C. However, BENEFITRO (σt ) ≥ 1
since RO uses lazy rejection. (This is the only part of the argument in which we use lazy rejection,
but this property is necessary since otherwise RO may reject every request when it begins the first
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 105–117 111
Y. A ZAR , A. B LUM , D.P. B UNDE , Y. M ANSOUR
A subphase.) Thus, BENEFITRO (σt ) ≥ (1/2)BENEFITA (σt ). After the first subphase, COSTR (σR ) ≤
(1/2)BENEFITA (σA ) since COSTR (σR ) ≤ 4k and BENEFITA (σA ) ≥ 8 · 4k−1 = 2 · 4k . Using this, we get
RO
BENEFIT (σt ) ≥ t − COSTA (σA ) − COSTR (σR )
≥ (t − tA ) + BENEFITA (σA ) − COSTR (σR )
≥ (t − tA ) + (1/2)BENEFITA (σA ) .
Since BENEFITA cannot increase faster than new requests arrive, BENEFITRO (σt ) ≥ (1/2)BENEFITA (σt ).
5 Combining admission control algorithms
In this section we briefly describe how to combine a collection of online algorithms into one master
algorithm that performs on any input sequence nearly as well as the best algorithm from the collection.
This is done separately for the acceptance problem and for the rejection problem. Results of this form
already exist in the literature [2, 7, 8, 11] but our main point here is that (a) these known techniques can
be applied in our abstract model, and (b) using our main result we can combine the two master algorithms
that result into one combined algorithm that guarantees both rejection and acceptance competitiveness.
The main ingredient in the combining algorithms is the process for switching between algorithms.
Note that switching algorithms might mean that we need to preempt some or all requests that we cur-
rently serve. In fact, the combining algorithms have a very different structure, depending on whether
they are minimizing the number of rejected requests or maximizing the number of accepted requests.
The algorithms to be combined can be either randomized or deterministic.
5.1 Combining algorithms to minimize rejection
First we show how to combine k (possibly preemptive) online algorithms R1 , R2 , . . . , Rk into a mas-
ter algorithm that for any sequence is reject-competitive with the best algorithm among the k for the
given sequence. For a sequence of requests σ let COST∗ (σ ) = mini COSTRi (σ ). We construct a deter-
ministic preemptive online combining algorithm REJdet such that for any σ , we have COSTREJdet (σ ) =
O(k COST∗ (σ )). We also provide a randomized preemptive online algorithm REJrand that guarantees
E COSTREJrand (σ ) = O(COST∗ (σ ) log k) .
The deterministic algorithm REJdet uses a simple greedy strategy. Let min(t) = min{COSTRi (σt )}.
The algorithm REJdet at time t follows one of the algorithms that made fewest rejections, i.e. min(t).
It preempts all the requests that the selected algorithm rejected or preempted. In the worst case REJdet
might reject k · min(t) requests up to time t, establishing the following theorem.
Theorem 5.1. The deterministic algorithm REJdet rejects at most k COST∗ (σ ) for any sequence σ of
requests.
The randomized algorithm REJrand uses a simple doubling strategy. Initially, it accepts all requests
as long as possible with no rejection and then sets λ = 1. When it is not possible to avoid a rejection,
it chooses a random i such that COSTRi (σ ) ≤ λ . Whenever the condition COSTRi (σ ) ≤ λ is violated, it
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 105–117 112
C OMBINING O NLINE A LGORITHMS FOR ACCEPTANCE AND R EJECTION
sets λ ← 2λ and chooses a random i such that Ri (σ ) ≤ λ . (If such a value of i does not exist then the
condition is immediately violated and we double the value of λ .)
To bound the performance of this algorithm, we observe that our problem can be reduced to the
problem of layered graph traversal of disjoint paths tied together at a common source. The input for
layered graph traversal is a weighted graph whose vertices are partitioned into sets L0 , L1 , . . . , Lk and
whose edges connect vertices in sets with adjacent indices. The objective is to move from a specified
source vertex in L0 to a specified target vertex in Lk . Initially, neither the target vertex nor the edge
weights are known to the algorithm. The weights of edges between Li and Li+1 become known when the
algorithm visits a vertex in Li . The target vertex becomes known when the algorithm visits a vertex in
Lk−1 . In the disjoint path version of the problem, the graph is the union of paths that are disjoint except
for the source vertex.
Our problem can be reduced to disjoint paths layered graph traversal on a graph where each path
corresponds to an algorithm and the ith edge on a path has weight equal to the number of requests
rejected when the ith request arrives. (Note that this cost can be more than one if the algorithms being
combined are preemptive since the arrival of a request may cause some previously-accepted requests to
be preempted.) Actually, the reduction is to a slight variation of the problem since we are allowed to
return to the common source with no cost and may only need to pay part of the cost when we switch
to another path. This can only reduce the competitive ratio since it may help the online algorithm but it
does not help the optimum (since the optimum does not switch between paths). Applying the results of
Fiat et al. [11] and Azar et al. [7] to our problem gives the following theorem:
Theorem 5.2. The expected number of requests rejected by randomized algorithm REJrand is at most
O(log k) times COST∗ (σ ) for any sequence of requests σ .
Clearly, we can apply the above theorems to a case where we have k algorithms and for each input
sequence σ there exists i such that E COST (σ ) ≤ cR COSTOPT (σ ):
R
i
Corollary 5.3. When constructed from k algorithms such that for any input sequence at least one al-
gorithm is cR -reject-competitive for that sequence, the deterministic algorithm REJdet is O(cR k)-reject-
competitive and the randomized algorithm REJrand is O(cR log k)-reject-competitive.
5.2 Combining algorithms to maximize acceptance
Now we show how to combine k non-preemptive algorithms A1 , A2 , . . . , Ak into a master algorithm that
is accept-competitive with the best algorithm among the k for the given sequence. For a sequence of
requests σ let A∗ (σ ) = maxi BENEFITAi (σ ). We construct one randomized preemptive online algorithm
ACC such that for any σ we have
E BENEFITACC (σ ) ≥ A∗ (σ )/ log k .
As before, we combine the algorithms by switching between them. When switching to a certain
algorithm we might need to preempt all requests we currently have, and in the worst case we are left with
a single accepted request. This suggests that there is no deterministic competitive combining algorithm
so we use randomization in our combining algorithm.
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 105–117 113
Y. A ZAR , A. B LUM , D.P. B UNDE , Y. M ANSOUR
The basic idea is that our generic model is a variant of the problem of picking a winner [2]. In the
problem of picking a winner we have k options (algorithms, in our setting). At any time some options
yield a benefit of one, while the others have a benefit of zero. (Negative benefits would be possible if
the algorithms being combined are preemptive, which is why we restrict our attention to non-preemptive
algorithms.) The decision maker (our combining algorithm) switches between options. When switch-
ing, the decision maker loses all its current benefit and gets, from that time on, the benefit of the current
option. Switching between options corresponds in our setting to switching between algorithms while
possibly preempting all currently accepted requests. It is shown by Awerbuch et al. [2] that using poly-
logarithmic number of switches, the decision maker achieves benefit at least a O(log k) fraction of the
benefit yielded by the best choice with high probability. Therefore,
Theorem 5.4. The expected number of requests accepted by the randomized algorithm ACC is at least
a O(log k) fraction of A∗ (σ ) for any sequence of requests σ .
As before, we can apply the above theorem to the case where we have k algorithms and for each
input sequence σ there exists i such that Ai (σ ) ≥ OPT(σ )/cA :
Corollary 5.5. When constructed from k algorithms such that for any input sequence at least one algo-
rithm is cA -accept-competitive for that sequence, the algorithm ACC is O(cA log k)-accept-competitive.
In fact, by slightly modifying the algorithm of Awerbuch et al. [2], allowing the combining algorithm
to disengage from all options, one can extend these results to the case of preemptive algorithms.
6 Conclusions and open problems
We have described procedures that take an algorithm A with competitive ratio cA for benefit, and an
algorithm R with competitive ratio cR for cost, produce an online algorithm that simultaneously achieves
competitive ratio O(cA ) for benefit and O(cA cR ) for cost. We do not know if it is possible in general to
do better. In particular, an ideal result in this direction would achieve O(cA ) for benefit and O(cR ) for
cost simultaneously.
Acknowledgements. The authors would like to thank the referees for their helpful comments. David
would like to acknowledge Sariel Har-Peled for help performing the analysis of S2 and RO when the
input algorithms are randomized.
References
[1] * R. A DLER AND Y. A ZAR: Beating the logarithmic lower bound: randomized preemp-
tive disjoint paths and call control algorithms. J. of Scheduling, pp. 113–129, 2003. Pre-
limary version in Proc. 10th ACM-SIAM Symp. on Discrete Algorithms, pp. 1–10, 1999.
[doi:10.1023/A:1022933824889, SODA:314500.314512, JSched:jq27641706456655]. 1.1
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 105–117 114
C OMBINING O NLINE A LGORITHMS FOR ACCEPTANCE AND R EJECTION
[2] * B. AWERBUCH , Y. A ZAR , A. F IAT, AND T. L EIGHTON: 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]. 1, 5, 5.2, 5.2
[3] * B. AWERBUCH , Y. A ZAR , AND S. P LOTKIN: Throughput-competitive online rout-
ing. In Proc. 34th IEEE Symp. on Foundations of Computer Science, pp. 32–40, 1993.
[FOCS:10.1109/SFCS.1993.366884]. 1.1
[4] * B. AWERBUCH , Y. BARTAL , A. F IAT, 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]. 1.1
[5] * B. AWERBUCH , R. G AWLICK , T. L EIGHTON , AND Y. R ABANI: 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].
1.1
[6] * Y. A ZAR , A. B LUM , AND Y. M ANSOUR: Combining online algorithms for rejection and accep-
tance. In Proc. 15th ACM Symp. Parallelism in Algorithms and Architectures, pp. 159–163, 2003.
[SPAA:10.1145/777412.777438]. 1, 2
[7] * Y. A ZAR , A. B RODER , AND M. M ANASSE: On-line choice of on-line algorithms. In Proc. 4th
ACM-SIAM Symp. on Discrete Algorithms, pp. 432–440, 1993. [SODA:313559.313847]. 1, 5, 5.1
[8] * R. BAEZA -YATES , J. C ULBERSON , AND G. R AWLINS: 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]. 1, 5
[9] * A. B LUM , A. K ALAI , AND J. K LEINBERG: Admission control to minimize rejections. In-
ternet Mathematics, 1(2):165–176, 2004. Preliminary version in Proc. 7th Workshop on Al-
gorithms and Data Structures, LNCS 2125, pp. 155–164, 2001. [WADS:9ukehq56d6yp2m22,
InternetMath:1(2):165–176]. 1.1
[10] * D.P. B UNDE AND Y. M ANSOUR: 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]. 1
[11] * A. F IAT, D. F OSTER , H. K ARLOFF , Y. R ABANI , Y. R AVID , AND S. V ISHWANATHAN: Com-
petitive 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]. 1, 5, 5.1
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 105–117 115
Y. A ZAR , A. B LUM , D.P. B UNDE , Y. M ANSOUR
AUTHORS
Yossi Azar
professor
School of Computer Science
Tel-Aviv University
Tel-Aviv, 69978, Israel
azar cs tau ac il
http://www.cs.tau.ac.il/~azar/
Avrim Blum
professor
Department of Computer Science
Carnegie Mellon University
Pittsburgh PA 15213-3891
avrim cs cmu edu
http://www.cs.cmu.edu/~avrim/
David P. Bunde
graduate student
Department of Computer Science
University of Illinois at Urbana-Champaign
Urbana, IL 61801
bunde uiuc edu
http://compgeom.cs.uiuc.edu/~bunde/
Yishay Mansour
professor
School of Computer Science
Tel-Aviv University
Tel-Aviv, 69978, Israel
mansour cs tau ac il
http://www.math.tau.ac.il/~mansour/
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 105–117 116
C OMBINING O NLINE A LGORITHMS FOR ACCEPTANCE AND R EJECTION
ABOUT THE AUTHORS
YOSSI A ZAR received his Ph.D. from Tel-Aviv University in 1989 (supervised by Noga
Alon). He spent several years in the Bay Area (Stanford, DEC, IBM); his experience
there included the Loma Prieta earthquake, 7.1 on the Richter scale. In 1994 he joined
the computer science faculty at Tel-Aviv University. He was the chair of the department
between 2002 and 2004. His main research interests are in the theory of algorithms,
especially online, randomized and approximation algorithms, as well as in trying to
understand his three children.
AVRIM B LUM grew up in Berkeley, CA, and then went to MIT for undergraduate and
graduate school. He received his Ph.D. in Computer Science under the supervision
of Ron Rivest, and now works in the family business. His research interests include
approximation algorithms, online algorithms, and machine learning theory. He has two
children, Alex and Aaron, who may or may not go into the family business.
DAVID B UNDE is currently pursuing his Ph.D. in the Computer Science department at the
University of Illinois in Urbana-Champaign, supervised by Jeff Erickson. Most of his
research has been on scheduling and processor allocation, though he also likes to work
on other algorithmic problems like the current paper and graph pebbling. In his spare
time, he enjoys reading and playing strategy games, particularly Civilization III.
Y ISHAY M ANSOUR obtained his B.A. in 1985 and his M.Sc. in 1987 at the Technion; his
M.Sc. advisor was Prof. Shmuel Zaks. He completed his Ph.D. at MIT in 1990 under
the supervision of Professors Shafi Goldwasser and Baruch Awerbuch. Subsequently
he became a postdoctoral fellow at Harvard University and a Research Staff Member at
IBM T.J. Watson Research Center. Since 1992 he has been with the School of Computer
Science at Tel-Aviv University, where he was the chairman during 2000-2002. His re-
search interests include online algorithms, communication networks, machine learning,
reinforcement learning and the theory of computation.
T HEORY OF C OMPUTING, Volume 1 (2005), pp. 105–117 117