Chapter 9. Competitive Analysis

In on-line computation an algorithm must make its decisions based only on past events without secure information on future. Such methods are called on-line algorithms. On-line algorithms have many applications in different areas such as computer science, economics and operations research.

The first results in this area appeared around 1970, and later since 1990 more and more researchers have started to work on problems related to on-line algorithms. Many subfields have been developed and investigated. Nowadays new results of the area have been presented on the most important conferences about algorithms. This chapter does not give a detailed overview about the results, because it is not possible in this framework. The goal of the chapter is to show some of the main methods of analysing and developing on-line algorithms by presenting some subareas in more details.

In the next section we define the basic notions used in the analysis of on-line algorithms. After giving the most important definitions we present one of the best-known on-line problems—the on-line -server problem—and some of the related results. Then we deal with a new area by presenting on-line problems belonging to computer networks. In the next section the on-line bin packing problem and its multidimensional generalisations are presented. Finally in the last section of this chapter we show some basic results concerning the area of on-line scheduling.

9.1. 9.1 Notions, definitions

Since an on-line algorithm makes its decisions based on partial information without knowing the whole instance in advance, we cannot expect it to give the optimal solution which can be given by an algorithm having full information. An algorithm which knows the whole input in advance is called off-line algorithm.

There are two main methods to measure the performance of on-line algorithms. One possibility is to use average case analysis where we hypothesise some distribution on events and we study the expected total cost.

The disadvantage of this approach is that usually we do not have any information about the distribution of the possible inputs. In this chapter we do not use the average case analysis.

An another approach is a worst case analysis, which is called competitive analysis. In this case we compare the objective function value of the solution produced by the on-line algorithm to the optimal off-line objective function value.

In case of on-line minimisation problems an on-line algorithm is called -competitive, if the cost of the solution produced by the on-line algorithm is at most times more than the optimal off-line cost for each input. The competitive ratio of an algorithm is the smallest for which the algorithm is -competitive.

For an arbitrary on-line algorithm ALG we denote the objective function value achieved on input by . The optimal off-line objective function value on is denoted by . Using this notation we can define the competitiveness as follows.

Algorithm ALG is -competitive, if is valid for each input .

There are two further versions of the competitiveness which are often used. For a minimisation problem an algorithm ALG is called weakly -competitive, if there exists such a constant that is valid for each input .

The weak competitive ratio of an algorithm is the smallest for which the algorithm is weakly -competitive.

A further version of the competitive ratio is the asymptotic competitive ratio. For minimisation problems the asymptotic competitive ratio of algorithm can be defined as follows:

An algorithm is called asymptotically -competitive if its asymptotic competitive ratio is at most .

The main property of the asymptotic ratio is that it considers the performance of the algorithm under the assumption that the size of the input tends to . This means that this ratio is not effected by the behaviour of the algorithm on the small size inputs.

Similar definitions can be given for maximisation problems. In that case algorithm ALG is called -competitive, if is valid for each input , and the algorithm is weakly -competitive if there exists such a constant that is valid for each input . The asymptotic ratio for maximisation problems can be given as follows:

The algorithm is called asymptotically -competitive if its asymptotic ratio is at least .

Many papers are devoted randomised on-line algorithms, in which case the objective function value achieved by the algorithm is a random variable, and the expected value of this variable is used in the definition of the competitive ratio. Since we consider only deterministic on-line algorithms in this chapter, we do not detail the notions related to randomised on-line algorithms.