% Authors: Yossi Azar, Avrim Blum, David P. Bunde, Yishay Mansour % Title: Combining Online Algorithms for Acceptance and Rejection \documentclass{toc} \usepackage{latexsym} \tocdetails{% volume=1, number=6, year=2005, firstpage=105, received={January 21, 2005}, published={September 14, 2005}} \newcommand{\comment}[1]{} \newcommand{\expect}[1]{E\left[#1\right]} \newcommand{\thresh}{\tau} \newcommand{\VA}{\text{\sc benefit}} %{B} \newcommand{\VR}{\text{\sc cost}} %{C} \newcommand{\cost}{\VR} \runningauthor{Y. Azar, A. Blum, D.P. Bunde, Y. Mansour} \runningtitle{Combining Online Algorithms for Acceptance and Rejection} \copyrightauthor{Yossi Azar, Avrim Blum, David P. Bunde, Yishay Mansour} \begin{document} \begin{frontmatter} \title{Combining Online Algorithms for Acceptance and Rejection} \tocpdftitle{Combining Online Algorithms for Acceptance and Rejection} \tocpdfauthor{Yossi Azar et. al.} \author[azar]{Yossi Azar\thanks{Research supported in part by the Israel Science Foundation and by the IST Program of the EU.}} \author[blum]{Avrim Blum\thanks{Research supported in part by NSF grants CCR-0105488, CCR-0122581, ITR IIS-0121678 and by a BSF grant.}} \author[bunde]{David P. Bunde\thanks{Research supported in part by NSF grant CCR-0093348.}} \author[mansour]{Yishay Mansour\thanks{Research supported in part by the Israel Science Foundation (grant No. 1079/04) and by a BSF grant.}} \begin{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 $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_R c_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. \end{abstract} \tockeywords{Algorithms, communication networks, resource allocation, online algorithms, competitive analysis, Quality of Service, admission control} \tocacm{F.2.2, C.2.2} % F.2.2 [Analysis of Algorithms and Problem Complexity]: % Nonnumerical Algorithms and Froblems C.2.2 [Computer-Communication % Networks]: Network Protocols---Routing protocols \tocams{68W05} %Computer Science---Algorithms---Nonnumerical algorithms \end{frontmatter} \section{Introduction} Resource allocation is one of the most critical tasks in communication networks. Many network resources 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 \emph{$c$-reject-competitive} if it rejects at most $c$ times the number of requests rejected by the optimal algorithm $OPT$ and \emph{$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 \emph{cost problem} and the maximization version is referred to as a \emph{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 \emph{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 decisions as we go. In this paper, we describe a procedure that given algorithms $A$ and $R$ that are $c_A$-accept-competitive and $c_R$-reject-competitive respectively, derives a combined algorithm that is simultaneously good under both measures. Specifically, the combined algorithm is simultaneously $O(c_A)$-accept-competitive and $O(c_Rc_A)$-reject-competitive.% \footnote{This paper is based on conference papers by Azar et al.~\cite{AzBlMa03} and Bunde and Mansour~\cite{BuMa04}. The first of these had a worse $O(c_A^2)$ guarantee on accept-competitiveness and furthermore needed to be given $c_A$ and $c_R$ 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(c_A)$ and removed the need to compute OPT or to know $c_A$ or $c_R$.} 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 \emph{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(c_A)$-accept-competitiveness and $O(c_Ac_R)$-reject-competitiveness, but the first needs to be given the value of $c_A$ in advance, while the second does not (neither needs to know $c_R$). 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.~\cite{BaCuRa93}, Fiat et al.~\cite{FFKRRV91}, and Azar et al.~\cite{AzBrMa93}. 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.~\cite{AwAzFL96}. These two combined algorithms can be combined to one master algorithm using our main result to guarantee both rejection and acceptance competitiveness. \subsection{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 \emph{capacity}, which is the maximum number of accepted requests that can use that edge. Adler and Azar~\cite{AdAz03} give a constant accept-competitive algorithm for the problem and Blum et al.~\cite{BlKaKl04} give a constant 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.~\cite{BlKaKl04} 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~\cite{AdAz03} 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.~\cite{AwBaFR94} and Awerbuch et al.~\cite{AGLR94} 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.~\cite{BlKaKl04} shows a constant competitive algorithm for the number of rejected requests in this case. By combining 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 logarithmic capacity and each request is for a fixed path. Awerbuch et al.~\cite{AwAzPl93} provide an $O(\log n)$-accept-competitive non-preemptive algorithm and Blum et al.~\cite{BlKaKl04} provide an $O(\log n)$-reject-competitive (preemptive) algorithm. We conclude there are algorithms simultaneously $O(\log n)$-accept-competitive and $O(\log^2 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. \section{Model} \label{section: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 $\sigma$ and algorithm $ALG$, let $\VA^{ALG}(\sigma)$ be the number of requests served by $ALG$ and $\VR^{ALG}(\sigma)$ 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. $\VA^{ALG}(\sigma)+\VR^{ALG}(\sigma)= |\sigma|$ for all algorithms $ALG$. An optimal algorithm $OPT$ can either maximize the benefit $\VA^{OPT}(\sigma)$ or minimize the cost $\VR^{OPT}(\sigma)$. 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 guarantees a competitive ratio of $c_A\geq 1$ for benefit. That is, for any sequence $\sigma$ \[ \expect{\VA^A(\sigma)} \geq \frac{1}{c_A} \VA^{OPT}(\sigma)\enspace. \] In addition, we are given a possibly randomized preemptive algorithm $R$ that has a guarantee of $c_R\geq 1$ for cost. That is, for any sequence $\sigma$ \[ \expect{\VR^R(\sigma)} \leq c_R \VR^{OPT}(\sigma)\enspace. \] \noindent{\bf Notation:} \comment{ Given an input sequence $\sigma$, denote by $\sigma_{(T+1,T+t)}$ the sequence of requests from time $T+1$ until time $T+t$. We also write $\sigma_{t}$ for $\sigma_{(1,t)}$. As a convention, the first request is number $1$. Given a subset $F$ of requests from $\sigma$ we denote by $\sigma_F$ the sub-sequence that includes only the requests of $F$. Given two sub-sequences $\sigma_1$ and $\sigma_2$ we denote by $\sigma_1 \sigma_2$ the combined sequence of requests, which first has the requests of $\sigma_1$ followed by the requests of $\sigma_2$. } Given an input sequence $\sigma$, denote by $\sigma_t$ the requests arriving by time $t$. As a convention, the first request is number $1$. \section{Algorithm S2} Now we describe $S2$, our first combining algorithm.\footnote{We call the algorithm $S2$ because it is based on and improves over a previous algorithm ``SWITCH''~\cite{AzBlMa03}.} Internally, $S2$ simulates algorithms $A$ and $R$ on the input $\sigma_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 $\VR^R(\sigma)$ (e.g., \lemref{lem1} and \lemref{lem2} 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 \emph{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 $\VR^R(\sigma_t)/t \leq \thresh$, where $\thresh = 1/(8c_A)$, 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. \subsection{Analysis of rejections} We define \emph{requests rejected because of algorithm $A$} to be the requests rejected or preempted during an $A$ phase (including those rejected when switching \emph{to} an $A$ phase) and denote their number at time $t$ with $R^A(\sigma_t)$. Thus, $\cost^{S2}(\sigma_t) \leq R^A(\sigma_t) + \cost^R(\sigma_t)$. \begin{lemma}\label{lem1} At any time $t$, $R^A(\sigma_t) < \VR^R(\sigma_t)/\thresh$. \end{lemma} \begin{proof} If $S2$ is in an $A$ phase at time $t$, $\VR^R(\sigma_t) > {\thresh}t$. Since algorithm $A$ cannot reject more than $t$ requests, $R^A(\sigma_t) \leq t < \VR^R(\sigma_t)/\thresh$. 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, $R^A(\sigma_T) < \VR^R(\sigma_T)/\thresh$. Since $S2$ has been in an $R$ phase since time $T+1$, $R^A(\sigma_t)=R^A(\sigma_T)$. Also, since the number of rejections of $R$ is a non-decreasing function of time, $\VR^R(\sigma_T) \leq \VR^R(\sigma_t)$. Thus, $R^A(\sigma_t) < \VR^R(\sigma_t)/\thresh$. \end{proof} Since $\cost^{S2}(\sigma_t) \leq R^A(\sigma_t) + \cost^R(\sigma_t)$, \lemref{lem1} implies that $$ \cost^{S2}(\sigma_t) \leq (1 + 1/\thresh)\cost^R(\sigma_t)\enspace. $$ 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 $c_R$-reject-competitive, we can bound the reject-competitive ratio of $S2$ by \[ \frac{\expect{\cost^{S2}(\sigma_t)}}{\cost^{OPT}(\sigma_t)} \; \leq \; \frac{\left(1+\frac{1}{\thresh}\right)\expect{\VR^R(\sigma_t)}}{\VR^{OPT}(\sigma_t)} \; \leq \; \left(1+\frac{1}{\thresh}\right)c_R \; = \; O(c_Ac_R)\enspace. \] \subsection{Analysis of acceptances} We define \emph{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 $R^R(\sigma_t)$. \begin{lemma}\label{lem2} At any time $t$, $R^R(\sigma_t) \leq \VA^{OPT}(\sigma_t)/(7c_A)$. \end{lemma} \begin{proof} If time $t$ is during an $R$ phase, the lemma follows from $$ \VA^{OPT}(\sigma_t) \geq \VA^R(\sigma_t) \geq (1-\thresh)t \geq 7t/8 $$ and $R^R(\sigma_t) \leq \VR^R(\sigma_t) \leq {\thresh}t = t/(8c_A)$. Consider time $t$ in an $A$ phase. If $S2$ has not had an $R$ phase, $R^R(\sigma_t)=0$ so the lemma holds. Otherwise, let $t'$ be the time at which the latest $R$ phase ended. By the argument above, $$ R^R(\sigma_{t'}) \leq \VA^{OPT}(\sigma_{t'})/(7c_A)\enspace. $$ Since $S2$ was in an $A$ phase since time $t'$, $$ R^R(\sigma_t) = R^R(\sigma_{t'}) \leq \VA^{OPT}(\sigma_{t'})/(7c_A)\enspace. $$ Since optimal benefit is non-decreasing with the input length, $R^R(\sigma_t) \leq \VA^{OPT}(\sigma_t)/(7c_A)$. \end{proof} Now we can prove that $S2$ is $O(c_A)$-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 $c_A$-accept-competitive, $\expect{\VA^A(\sigma)} \geq \VA^{OPT}(\sigma)/c_A$. By \lemref{lem2}, algorithm $R$ causes $R^R(\sigma_t) \leq \VA^{OPT}(\sigma)/(7c_A)$ additional rejections. Thus, $$ \expect{\VA^{S2}(\sigma)} \geq \VA^{OPT}(\sigma)/c_A - \VA^{OPT}(\sigma)/(7c_A) = (6/(7c_A)) \VA^{OPT}(\sigma) $$ and the accept-competitive ratio of $S2$ is at most $(7/6)c_A = O(c_A)$. \section{Algorithm RO} Now we define $RO$, our second combining algorithm.\footnote{ We call this algorithm $RO$ for Ratio Oblivious because it does not need to know the competitive ratios of the input algorithms.} One problem with our previous algorithm $S2$ is that, while simple, it required knowing $c_A$ in advance. Algorithm $RO$ is a bit more complicated but does not need to be given either of the competitive ratios as input. Internally, algorithm $RO$ keeps times $t_A$ and $t_R$, plus input prefixes $\sigma_A$ and $\sigma_R$ of these lengths. It maintains simulations of algorithms $A$ and $R$ on inputs $\sigma_A$ and $\sigma_R$ respectively. Whenever either of these algorithms decides to reject a request, that request is marked. Times $t_A$ and $t_R$ advance in phases, pausing and resuming the simulations as necessary so that $\max\{t_A,t_R\}=t$ at time $t$. Specifically, phase $k\geq 0$ has an $R$ subphase, during which time $t_R$ advances until $\VR^R(\sigma_R) = 4^k$, followed by an $A$ subphase, during which time $t_A$ advances until $\VA^A(\sigma_A)= 8 \cdot 4^k$ (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\{t_A,t_R\}=t$). The idea of using marks to delay rejections as long as possible is called \emph{lazy rejection}. \subsection{Analysis of rejections} To analyze rejections, we first show that the algorithm maintains the invariant that $\VA^A(\sigma_A)$ $ \leq 32 \VR^R(\sigma_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 $\VA^A(\sigma_A)=0$. During the first $A$ subphase, $\VR^R(\sigma_R) = 1$ and $\VA^A(\sigma_A) \leq 8$. Finally, during phases after the first, $\VR^R(\sigma_R) \geq 4^{k-1}$ and $\VA^A(\sigma_A) \leq 8 \cdot 4^k$. Using the above inequality, we can bound $\VR^A(\sigma_A)$ from above by \begin{eqnarray*} \VR^A(\sigma_A) \; \leq \; t_A & = & \VR^{OPT}(\sigma_A)+\VA^{OPT}(\sigma_A) \\ & \leq & \VR^{OPT}(\sigma_A)+c_A\expect{\VA^A(\sigma_A)} \\ & \leq & \VR^{OPT}(\sigma_A)+32c_A\expect{\VR^R(\sigma_R)}\ . \end{eqnarray*} Thus, the rejection competitive ratio of $RO$ is at most \[ \frac{\expect{\VR^A(\sigma_A)+\VR^R(\sigma_R)}}{\VR^{OPT}(\sigma_t)} \leq 1 + \frac{32c_A\expect{\VR^R(\sigma_R)}}{\VR^{OPT}(\sigma_t)} + c_R = O(c_Ac_R) \ . \] \subsection{Analysis of acceptances} To show that algorithm $RO$ is $O(c_A)$-accept-competitive, we show $$ \VA^{RO}(\sigma_t) \geq (1/2)\VA^{A}(\sigma_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 $\VA^{RO}(\sigma_t) = \VA^{A}(\sigma_t)$. The first $A$ subphase begins when algorithm $R$ rejects (or preempts) a request $C$. Algorithm $RO$ accepts the same requests as algorithm $A$ except possibly for $C$. However, $\VA^{RO}(\sigma_t) \geq 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 $A$ subphase.) Thus, $\VA^{RO}(\sigma_t) \geq (1/2)\VA^{A}(\sigma_t)$. After the first subphase, $\VR^R(\sigma_R) \leq (1/2)\VA^A(\sigma_A)$ since $\VR^R(\sigma_R) \leq 4^k$ and $\VA^A(\sigma_A) \geq 8 \cdot 4^{k-1} = 2 \cdot 4^k$. Using this, we get \begin{eqnarray*} \VA^{RO}(\sigma_t) & \geq & t - \VR^A(\sigma_A) - \VR^R(\sigma_R) \\ & \geq & (t-t_A) + \VA^A(\sigma_A) - \VR^R(\sigma_R) \\ & \geq & (t-t_A) + (1/2)\VA^A(\sigma_A)\enspace. \end{eqnarray*} Since $\VA^A$ cannot increase faster than new requests arrive, $\VA^{RO}(\sigma_t) \geq (1/2)\VA^A(\sigma_t)$. \section{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 \cite{AwAzFL96,AzBrMa93,BaCuRa93,FFKRRV91} 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 currently 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. \subsection{Combining algorithms to minimize rejection} First we show how to combine $k$ (possibly preemptive) online algorithms $R_1, R_2, \ldots, R_k$ into a master algorithm that for any sequence is reject-competitive with the best algorithm among the $k$ for the given sequence. For a sequence of requests $\sigma$ let $\VR^*(\sigma)=\min_i \VR^{R_i}(\sigma)$. We construct a deterministic preemptive online combining algorithm $REJ_{det}$ such that for any $\sigma$, we have $\VR^{REJ_{det}}(\sigma)= O(k\VR^*(\sigma))$. We also provide a randomized preemptive online algorithm $REJ_{rand}$ that guarantees \[ \expect{\VR^{REJ_{rand}}(\sigma)} = O(\VR^*(\sigma)\log k)\enspace. \] The deterministic algorithm $REJ_{det}$ uses a simple greedy strategy. Let $\min(t) = min\{\VR^{R_i}(\sigma_{t})\}$. The algorithm $REJ_{det}$ 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 $REJ_{det}$ might reject $k\cdot min(t)$ requests up to time $t$, establishing the following theorem. \begin{theorem} The deterministic algorithm $REJ_{det}$ rejects at most $k\VR^*(\sigma)$ for any sequence $\sigma$ of requests. \end{theorem} The randomized algorithm $REJ_{rand}$ uses a simple doubling strategy. Initially, it accepts all requests as long as possible with no rejection and then sets $\lambda=1$. When it is not possible to avoid a rejection, it chooses a random $i$ such that $\VR^{R_i}(\sigma)\leq \lambda$. Whenever the condition $\VR^{R_i}(\sigma)\leq \lambda$ is violated, it sets $\lambda \gets 2\lambda$ and chooses a random $i$ such that $R_i(\sigma)\leq \lambda$. (If such a value of $i$ does not exist then the condition is immediately violated and we double the value of $\lambda$.) To bound the performance of this algorithm, we observe that our problem can be reduced to the problem of \emph{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 $L_0, L_1, \ldots, L_k$ and whose edges connect vertices in sets with adjacent indices. The objective is to move from a specified source vertex in $L_0$ to a specified target vertex in $L_k$. Initially, neither the target vertex nor the edge weights are known to the algorithm. The weights of edges between $L_i$ and $L_{i+1}$ become known when the algorithm visits a vertex in $L_i$. The target vertex becomes known when the algorithm visits a vertex in $L_{k-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 $i^\text{th}$ edge on a path has weight equal to the number of requests rejected when the $i^\text{th}$ 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.~\cite{FFKRRV91} and Azar et al.~\cite{AzBrMa93} to our problem gives the following theorem: \begin{theorem} The expected number of requests rejected by randomized algorithm $REJ_{rand}$ is at most $O(\log k)$ times $\VR^*(\sigma)$ for any sequence of requests $\sigma$. \end{theorem} Clearly, we can apply the above theorems to a case where we have $k$ algorithms and for each input sequence $\sigma$ there exists $i$ such that $\expect{\VR^{R_i}(\sigma)} \leq c_R \VR^{OPT}(\sigma)$: \begin{corollary} When constructed from $k$ algorithms such that for any input sequence at least one algorithm is $c_R$-reject-competitive for that sequence, the deterministic algorithm $REJ_{det}$ is $O(c_R k)$-reject-competitive and the randomized algorithm $REJ_{rand}$ is $O(c_R\log k)$-reject-competitive. \end{corollary} \subsection{Combining algorithms to maximize acceptance} Now we show how to combine $k$ non-preemptive algorithms $A_1, A_2, \ldots, A_k$ into a master algorithm that is accept-competitive with the best algorithm among the $k$ for the given sequence. For a sequence of requests $\sigma$ let $A^*(\sigma)=\max_i \VA^{A_i}(\sigma)$. We construct one randomized preemptive online algorithm $ACC$ such that for any $\sigma$ we have \[ \expect{\VA^{ACC}(\sigma)} \geq A^*(\sigma)/\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. The basic idea is that our generic model is a variant of the problem of picking a winner \cite{AwAzFL96}. 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 switching, 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.~\cite{AwAzFL96} that using polylogarithmic 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, \begin{theorem} The expected number of requests accepted by the randomized algorithm $ACC$ is at least a $O(\log k)$ fraction of $A^*(\sigma)$ for any sequence of requests $\sigma$. \end{theorem} As before, we can apply the above theorem to the case where we have $k$ algorithms and for each input sequence $\sigma$ there exists $i$ such that $A_i(\sigma)\geq \text{OPT}(\sigma)/c_A$: \begin{corollary} When constructed from $k$ algorithms such that for any input sequence at least one algorithm is $c_A$-accept-competitive for that sequence, the algorithm $ACC$ is $O(c_A\log k)$-accept-competitive. \end{corollary} In fact, by slightly modifying the algorithm of Awerbuch et al.~\cite{AwAzFL96}, allowing the combining algorithm to disengage from all options, one can extend these results to the case of preemptive algorithms. \section{Conclusions and open problems} We have described procedures that take an algorithm $A$ with competitive ratio $c_A$ for benefit, and an algorithm $R$ with competitive ratio $c_R$ for cost, produce an online algorithm that simultaneously achieves competitive ratio $O(c_A)$ for benefit and $O(c_Ac_R)$ 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(c_A)$ for benefit and $O(c_R)$ for cost simultaneously. \paragraph{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. \bibliographystyle{tocplain} \bibliography{a006} \begin{tocauthors} \begin{tocinfo}[azar]% Yossi Azar \\ professor \\ School of Computer Science \\ Tel-Aviv University \\ Tel-Aviv, 69978, Israel \\ azar\tocat{}cs\tocdot{}tau\tocdot{}ac\tocdot{}il \\ \url{http://www.cs.tau.ac.il/~azar/} \end{tocinfo} \begin{tocinfo}[blum]% Avrim Blum \\ professor \\ Department of Computer Science \\ Carnegie Mellon University \\ Pittsburgh PA 15213-3891 \\ avrim\tocat{}cs\tocdot{}cmu\tocdot{}edu \\ \url{http://www.cs.cmu.edu/~avrim/} \end{tocinfo} \begin{tocinfo}[bunde]% David P. Bunde \\ graduate student \\ Department of Computer Science \\ University of Illinois at Urbana-Champaign \\ Urbana, IL 61801 \\ bunde\tocat{}uiuc\tocdot{}edu \\ \url{http://compgeom.cs.uiuc.edu/~bunde/} \end{tocinfo} \begin{tocinfo}[mansour]% Yishay Mansour \\ professor \\ School of Computer Science \\ Tel-Aviv University \\ Tel-Aviv, 69978, Israel \\ mansour\tocat{}cs\tocdot{}tau\tocdot{}ac\tocdot{}il \\ \url{http://www.math.tau.ac.il/~mansour/} \end{tocinfo} \end{tocauthors} \begin{tocaboutauthor} \begin{tocabout}[azar] {\sc Yossi Azar} received his Ph.D. from \href{http://www.cs.tau.ac.il/}{Tel-Aviv University} in 1989 (supervised by \href{http://www.cs.tau.ac.il/~nogaa/}{Noga Alon}). He spent several years in the Bay Area (Stanford, DEC, IBM); his experience there included the \href{http://quake.wr.usgs.gov/prepare/future/index.html}{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. \end{tocabout} \begin{tocabout}[blum] {\sc Avrim Blum} 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 \href{http://theory.lcs.mit.edu/~rivest}{Ron Rivest}, and now works in the \href{http://www.cs.cmu.edu/~mblum}{family} \href{http://www.cs.cmu.edu/~lblum}{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. \end{tocabout} \begin{tocabout}[bunde] {\sc David Bunde} is currently pursuing his Ph.D. in the Computer Science department at the University of Illinois in Urbana-Champaign, supervised by \href{http://compgeom.cs.uiuc.edu/~jeffe/}{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 \href{http://mingus.la.asu.edu/~hurlbert/pebbling/pebb.html}{graph pebbling}. In his spare time, he enjoys reading and playing strategy games, particularly \href{http://www.civ3.com/}{Civilization III}. \end{tocabout} \begin{tocabout}[mansour] {\sc Yishay Mansour} obtained his B.A. in 1985 and his M.Sc. in 1987 at the Technion; his M.Sc. advisor was Prof. \href{http://www.cs.technion.ac.il/People/Faculty/zaks.html}{Shmuel Zaks}. He completed his Ph.D. at MIT in 1990 under the supervision of Professors \href{http://theory.lcs.mit.edu/~shafi}{Shafi Goldwasser} and \href{http://www.cs.jhu.edu/~baruch}{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 research interests include online algorithms, communication networks, machine learning, reinforcement learning and the theory of computation. \end{tocabout} \end{tocaboutauthor} \end{document}