Online request server matching.
In the following paper an alternative online variant of the matching problem in bipartite graphs is presented. It is triggered by a scheduling problem. There, a task is unknown up to its disclosure. However, when a task is revealed, it is not necessary to take a decision on the service of that particular task. On the contrary, an online scheduler has to decide on how to use the current resources. Therefore, the problem is called online request server matching (ORSM). It differs substantially from the online bipartite matching problem of Karp et al. (Proc. 22nd Annual ACM Symp. on Theory of Computing, Baltimore, Maryland, May 14-16, 1990, ACM Press, New York, 1990). Hence, the analysis of an optimal, deterministic online algorithm for the ORSM problem results in a smaller competitive ratio of 1.5. An extension to a weighted bipartite matching problem is also introduced, and results of its investigation are presented. Additional concepts for the ORSM model (e.g. lookahead, parallel resources, deadlines) are studied. All of these modifications are realized by restrictions on the input structure. Decreased competitive ratios are presented for some of these modified models. Copyright 2001 Elsevier Science B.V.
Introduction
In this report we study a model which was developed for a rather simple scheduling problem.
Consider a single resource and a discrete time model. The resource is available for one unit
in every time step. In the following this resource is called server. Every time step a task
can occur that has a demand of one unit of the server. This task is called request. Such
a request includes a set of time steps which specifies acceptable times for serving. These
times must not be situated in the past and neither need to be consecutive nor include the
time step of the arrival of the request. It is obvious that we can model this problem by a
bipartite graph (R
E). The two disjoint partitions represent the server resource
at every time step (S) and the set of requests (R). Whenever a request r 2 R can be
served at time j, there is an edge fr; sg between request vertex r and the vertex s 2 S
which represents the j-th time step. Then the problem to decide when a request should
be served is nothing else than to construct a matching in G.
Our scheduling problem is online, i. e. the requests appear through time while the current
usage of the server has to be determined. These decisions have to be made without knowledge
of further requests and cannot be taken back. The definition of our problem implies
that in general it is impossible to serve all requests 1 . Additionally, the lack of information
about the future prevents an optimal solution to be found which maximizes the number of
successful requests.
This online matching problem in a bipartite graph is called online request server matching
(ORSM).
We make use of competitive analysis to investigate the described problem. Here the worst
case factor between the quality of an optimal solution and a solution calculated by an
online algorithm on the same input is determined. This factor is called competitive ratio.
For our matching problem the size of a maximum matching in G is the value of the optimal
solution. It is well-known how to calculate it in O(
(see [ET75] or any
comprehensive textbook on algorithms).
In this report we present an optimal online algorithm which constructs a matching of at
least 2of the maximal size. We also investigate a weighted variant of this online matching
problem. Then all edges have a weight and the objective is the construction of a maximal
weighted matching. For this problem our analysis shows a lower bound of
and an upper bound of 2 for the competitive ratio.
The material of this report is organized as follows. The next subsection presents a short
introduction to competitive analysis. Thereafter, an overview of related work is given.
Section 2 defines our model formally. It will be compared precisely with two models that
have been studied in literature. Additionally, a few definitions and notations are given in
the end. The simple, unweighted variant of our model is analysed in Sect. 3. It includes
a general lower bound for the competitive ratio, a deterministic online algorithm, and a
matching upper bound. Section 4 investigates the weighted version of this problem. The
proof of a general lower bound is followed by the presentation of an algorithm. Its tight
Imagine two requests to exactly the same, single server resource.
analysis establishes a gap to the previous lower bound. The section ends with some remarks
and a suggestion for a more sophisticated online algorithm. This report is completed by a
description of a few open problems.
1.1 Competitive Analysis
Algorithms are often based on the principle of the following sequence: input, computation,
and output. After reading the complete input, which is a description of a finite problem,
it computes a solution and presents it at the end. Such a behaviour is called offline.
In real world applications like e. g. embedded systems we find different requirements.
Here, parts of the input appear by and by for an indefinite period of time and decisions
of the solution have to be made immediately without knowing the future. These types
of problems, including their solving algorithms, are called online. Different methods were
suggested to analyse such online algorithms.
The most popular methods of the past, which are still in use, assume a known input
distribution (a stochastic model for the input). Of course, the expressiveness of results of
these studies are highly dependent on the correct choice of the distribution.
In contrast 1984 Daniel D. Sleator and Robert E. Tarjan introduced a new method for
analysing online algorithms (journal version is [ST85]). It is a method of worst case analysis
which avoids these difficulties and has been becoming more and more popular in the last
decade.
The basic idea is a comparison of the quality of the solution computed by the online
algorithm and the quality of an optimal, offline solution for the same input.
Let A be an online algorithm and let OPT be an optimal offline algorithm for a payoff
maximization problem 2 . Then, for an input sequence oe we denote with perf A (oe) the
performance of the algorithm A and perf OPT (oe) is the performance of OPT respectively.
A is called c-competitive if there is a constant ff such that
The constant ff has to be independent of the input and can compensate irregularities right
at the beginning. Then the infimum over all values c such that A is c-competitive is called
the competitive ratio of A. Whenever the constant alternatively define the
competitive ratio as
sup
oe
perf OPT (oe)
perf A (oe)
2 In this report we do not consider problems which have to minimize costs. The definitions would slightly
differ to ensure that a competitive ratio is always at least 1.
We immediately realize that this analysis is independent of a stochastic model for the inputs
and gives performance guarantees. On the other hand this kind of analysis is sometimes
unrealistically pessimistic.
Indeed, an online algorithm approximates an optimal solution while working under the
restriction of incomplete knowledge. So the distinguished name competitive ratio for the
approximation factor seems to be adequate.
An excellent, introductory article on competitive analysis is [Kar92]. A comprehensive
introduction is the textbook by Allan Borodin and Ran El-Yaniv [BEY98] which includes
an extensive bibliography.
Two essential techniques to prove competitive ratios have been established. A description
of these methods illustrates the character of this type of analysis.
Lower bounds for the competitive ratio are typically shown by an adversary strategy.
We can interpret competitive analysis as a game between an online algorithm A and an
omniscient adversary. The adversary creates the input sequence oe with knowledge of A.
So it can in advance calculate every decision of A on oe, perf A (oe), and perf OPT (oe). Due
to the unlimited computational power the malicious adversary is able to construct a worst
case input sequence.
When we derive general lower bounds for the competitive ratio of a problem we slightly
change our view. Then a strategy is given which tells the adversary how to construct
the next part of the input sequence dependent on the decisions an online algorithm was
able to make. The performance analysis of these sequences gives a lower bound for the
competitive ratio when the strategy is able to generate infinite inputs. Otherwise the loss
of performance of an online algorithm could be compensated by the constant ff in the
above definition.
To prove upper bounds for an online problem the performance of a designed algorithm A
is investigated. Sometimes, ad hoc arguments can be applied to show how A can bound
the competitive ratio. However, it is more common to apply a potential function argument
for an analysis of amortized performance. Hence, every pair of a state of A and a state of
OPT is mapped to a real value by a potential function \Phi. Whenever it can be shown that
for every step i with input oe i holds
and \Phi is bounded above, then A is c-competitive. It was shown that there exists such
a potential function for every online algorithm (see the description in [IK96], page 534).
Nevertheless the variant usage of potential functions and combinations with additional
arguments are nowadays commonly used in proofs of the performance of online algorithms.
Several extensions of the competitive analysis were suggested. A major influence had the
seminal work [BDBK + 94] which introduces randomized online algorithms and adapted
methods for their analysis. However, in this report we limit our study to deterministic
online algorithms.
1.2 Previous Work
We introduced our online problem in terms of a scheduling problem. However, there is a
vast literature on the subject of online scheduling and related problems like load balancing
and routing. We will not review these works here. The reader may consult the survey by
instead. The publications of online matching problems are more relevant
to the studies of this report. In the following, we discuss these papers.
The first article about an online version of a bipartite matching problem is by Richard M.
Karp, Umesh V. Vazirani and Vijay V. Vazirani [KVV90]. The partition U of the graph
E) is known in advance and the vertices of V including their edges arrive
through time. Whenever a vertex v 2 V is revealed, an online algorithm has to decide which
edge incident to v is added to the online matching M . The objective is the maximization
of the size of M . For deterministic online algorithms the competitive ratio is exactly 2.
An adversary can present an input with a vertex being adjacent to two vertices
After the decision of the online algorithm, the adversary presents vertex
which is adjacent to the previous matched vertex u or u 0 , only. The online algorithm is
not able to match v 1 and v 2 . However, there is such an offline solution. The infinite
repetition of this strategy results in the lower bound of 2. The greedy algorithm which
adds the first possible edge of an incoming vertex to the matching M achieves this
competitive ratio. From graph theory we know that this greedy algorithm constructs a
maximal matching (every edge of the graph is either itself a matching edge or is adjacent
to one) and every maximal matching has at least half the size of an optimal, maximum
matching.
The key contribution of the discussed paper is the analysis of a randomized online algorithm
for the described problem.
Ming-Yang Kao and Stephen R. Tate investigated the above model with blocked inputs
[KT91]. When an input occurs k vertices were revealed 'in a block' instead of one at a
time. Let be the number of vertices in the partition V of the bipartite graph. Of
course with the problem is the same as above and for we have the offline
version of the matching problem. For deterministic online algorithms, no improvements
are possible as long as k - n. For randomized algorithms the result of [KVV90] cannot
be improved apart from low order terms as long as
The online b-matching was analysed by Bala Kalyanasundaram and Kirk Pruhs in [KP95].
In this problem the vertices of the partition V can be incident to at most b edges out of
the matching. Again, the size of the matching has to be maximized. The authors give an
optimal deterministic algorithm with competitive ratio
A weighted variant of the online bipartite matching was studied by the same authors
in [KP93]. When allowing an arbitrary weight function for the edges, no competitive
algorithm can exist. To see this consider that an online algorithm has chosen a matching
edge of weight one. As a next step an adjacent edge of arbitrary weight is revealed. Then
no online algorithm can bound the competitive ratio.
Hence, the model was restricted to a weighted, complete bipartite graph of partitions of
equal which is a metric space (especially the triangle inequation is
fulfilled). When asked for a maximal weighted matching, the greedy algorithm is optimal
and 3-competitive.
On the other hand in the minimum weighted matching problem, a perfect matching of
minimal weight has to be determined in a bipartite graph defined as above. Then an
optimal and (2n \Gamma 1)-competitive algorithm is shown. The same result was independently
discovered by Samir Khuller, Stephen G. Mitchell and Vijay V. Vazirani in [KMV94] 3 . The
last article also contains a study of an online version of the stable marriage problem.
In [ANR95] Yossi Azar, Joseph Naor and Raphael Rom studied a different model based on
bipartite graphs. They called it online assignment. The partition U has a fixed size and
vertices out of V are adjacent to a subset of U . For each v 2 V one of its weighted edge
must be selected immediately after its arrival with the objective to minimize the maximal
weight of all selected edges incident to a vertex in U . Indeed, this is a load balancing
problem. For deterministic online algorithms a lower bound of dlog 2
1)e and an upper
bound of dlog 2 ne shown for the competitive ratio.
The technical report by Ethan Bernstein and Sridhar Rajagopalan [BR93] is of major
importance for our following studies. An online matching problem in general graphs called
roommates problem has been introduced. The graph is undirected, simple
and weighted. An unweighted version of this model has also been investigated.
The input sequence consists of the vertices of V . Whenever a vertex is revealed, all of its
adjacent vertices and the weighted edges in between become known. We want to emphasize
that this process includes adjacent vertices never seen before in the input sequence. Then,
an edge of the current vertex to a non-matched vertex (that has been revealed previously)
can be added to the online matching. An edge to a non-revealed and incompletely known
vertex can be selected later when this adjacent vertex is the current one in the input
sequence.
For the roommates problem the unweighted model is interpreted as follows: People arrive
one at a time to a hotel where a conference takes place. The hotel consists of double
rooms, only. Every person gives a list of possible roommates independently of whether
they have arrived yet. The model assumes that these lists are symmetric, i. e., every
potential roommate will accept to share this room. The hotel manager has to decide in
which room the person will stay. The objective is to minimize the allocated rooms, i. e. to
maximize the matching in the implicitly defined graph.
In the weighted version the aim is an online construction of a weighted matching of maximal
size in G.
In the paper a tight analysis of the unweighted model is given. Therefore the competitive
ratio is 1:5 : For the weighted model a lower bound of 3 is proven. A suggested online
algorithm is shown to be 4-competitive.
3 Both articles ([KP93] and [KMV94]) were previously published on conferences in 1991.
At the end of the next section we will revisit the roommates problem and we will compare
it to our model. Indeed, our model is a special case of the roommates problem. For our
investigations we were able to adapt proofs taken from the discussed paper.
2 The Model
In the beginning of the introduction we described an online matching problem. Now we
will present a formal definition for the online request server matching problem (ORSM).
The underlying structure of the problem is a bipartite graph G := (R :
E). Both
partitions R and S are totally ordered. We denote the vertices by r
and the indices indicate the position within the order.
We interpret this order as a discrete time model. The vertices of partition S represent a
simple resource called server, which is available for one unit each time step. Partition R is
interpreted as a set of tasks. Such a task has a demand of one server unit to be completed.
We call them requests and every time step one of them might occur. An edge fr
between a request vertex r i and a server vertex s j means that the request can be served in
time step j. The set of edges E ae R \Theta S is constructed with a restriction:
This means that a request that occurs at time step i must not specify a possible service
time in the past. Without this restriction the modelled scheduling problem does not make
sense and no competitive online algorithm would be possible.
Now we have to specify how this model works online: When the system starts the partition
R is completely unknown 4 . In the beginning of a time step i the request r i is revealed as
input, i. e. the vertex r i and all of its edges are inserted into the previous known part of
G. If no request appears, vertex r i is isolated.
After this input, an algorithm has to decide how to use the server in the current time step
i. Indeed, it can add an edge incident to s i to the online matching M . It is worth noting
that due to the restriction (1) all edges incident to s i are known when this decision has
to be made. The online algorithm has the objective to maximize the cardinality of the
matching M , i. e. to serve as much requests as it can.
Up to now the graph G was unweighted. We also study the weighted variant. Then
the graph is defined as G := (R
w). The weight function defines a
positive real value for every edge. The objective is the construction of a weighted matching
of maximal overall weight. Otherwise, the problem and its online fashion is completely the
same as in the ORSM problem. This version is named online request server weighted
matching problem or in short wORSM problem.
4 When we take a close look this is not the truth. We know that every time step i a new vertex r i is
inserted but its set of incident edges is unknown before. For our convenience we will interpret the input
process in the introduced way.
2.1 Our Model in Comparison with Models out of Literature
At first we want to make a clear distinction between the ORSM model and the online
bipartite matching problem in [KVV90]. In the later one the vertices from the unknown
partition and their edges appear in the same way as in the ORSM problem. However, in the
online bipartite matching problem no order on the vertices of the already known partition
is given and no restrictions on the set of edges. After a new vertex v is inserted the online
algorithm has to decide which edge incident to v should be added to the matching. In
contrast, in the ORSM model, one asks for an edge incident to the current server vertex to
add into the matching. This server vertex is situated in the known partition of the bipartite
graph. The restriction (1) of the set of edges guarantees that all edges of this server vertex
are known at that time. Due to the specified input process (revealing a request vertex and
all of its edges), all adjacent edges are known as well. There is therefore the advantage to
have some extra knowledge of the graph structure whenever a decision has to be taken.
That is also the reason why it is possible to achieve a better competitive ratio for the
ORSM problem. Additionally, in the weighted version, a restriction on a metric space, or
the other restrictions described in Sect. 1.2 are not necessary.
Again, we want to emphasize the difference: In the online bipartite matching problem
decisions about adding an edge to the online matching are made with respect to a set of
edges incident to a just revealed vertex. In the ORSM problem such a decision is made
with respect to a set of edges incident to a vertex of the other (known) partition.
In the previous section it was claimed that the ORSM problem is a special case of the
roommates problem. Now we are able to give a transformation of an instance of the wORSM
problem with its bipartite graph (R
to an instance of the roommates
problem with the underlying graph its total order OE on the set VR .
This transformation defines:
VR
and the order OE on VR is defined by the use of the orders on R and S such that:
Whenever a vertex r i is inserted, the roommates problem on GR is not able to add any edge
to M because no adjacent s-vertices are revealed (remember restriction (1) on E). Then
vertex s i is inserted. All of its incident edges and adjacent vertices respectively, are known
at that time and so every edge of s i can be selected as a matching edge in the roommates
problem. No edge of an unrevealed vertex was given simultaneously. That means s i will
never be a candidate for the matching again. We conclude that the roommates problem
can simulate the wORSM problem using the given transformation.
Nevertheless, the two models are not able to simulate each other. Hence, we have to
prove the lower bound of the competitive ratio for our more restrictive model. Additional
we present an online algorithm and an analysis applying simplified arguments which are
tailor-made to the ORSM problem. In the weighted model, the increase in knowledge of
the graph structure, compared to the roommates problem, results in a lower value for the
competitive ratio.
Before starting our investigations a few definitions and notations are presented.
2.2 Definitions and Notations
Although we assume that the reader is familiar with basic concepts in graph theory, and
although we already used some graph theoretical notations, a few standard definitions are
included in the following list.
(weighted graph)
is called a weighted graph iff
V is a finite set of vertices,
is a set of edges, and
is a weight function.
When using the unit weight function an unweighted graph E) is
derived. As you can see, the weight function is omitted in the notation. This conversation
from a weighted to an unweighted graph applies to the next definitions of graphs and
matchings.
Bipartite graphs consist of two disjoint sets of vertices without edges inside the sets:
Definition 3 (bipartite weighted graph)
is called a bipartite weighted graph iff
U and V are finite sets of vertices,
is a set of edges, and
is a weight function.
Definition 4 (vertex induced subgraph)
be a weighted graph and V S ae V . Then
:=
is the subgraph of G induced by vertex set
be a weighted graph. M is called a matching in G iff
Definition 6 (weight of a matching, jM
be a weighted graph and let M be a matching in G.
w(fu; vg)
is called the weight of matching
It is obvious that jM j counts the number of edges in M when it is applied to an unweighted
graph. In that case jM j is called the cardinality or size of the matching M :
E) be a graph and let M ae E be a matching. For
Definition 8 (maximum weighted matching, M(G))
be a weighted graph. Then M(G) denotes a maximum weighted matching

We will frequently denote a specially defined or calculated maximum matching by
Definition 9 (symmetric difference, \Phi)
Let A and B be two sets. Then A \Phi B denotes the symmetric difference:
To illustrate structures of graphs and matchings, we use a graphical notation. It is fully
interchangeable with the set theoretical representation. Vertices of the two sets in bipartite
graphs were depicted by small, filled circles
v and squares respectively. The circles
represent vertices from the request partition R, and squares represent vertices out of the
server partition S. Additionally, the label of such a vertex is written right next to its
symbol. When we sketch an instance of the wORSM problem, the vertices of the request
partition are drawn in their order along a horizontal line from left to right. The server
vertices are drawn in the same way in a distance below. Indeed, a request vertex is situated
precisely on top of the server vertex of the same time step:
Edges are depicted by a line between two vertices. Of course in bipartite graphs such a
line has a circle and a square on its ends:
To mark the edges of a matching they are symbolized by a double line:
Whenever edges cannot be selected for the matching anymore, due to previous decisions
made by the online algorithm, they were depicted in grey:
3 The Online Request Server Matching Problem
This section starts with a general lower bound for the competitive ratio of the ORSM
problem for deterministic online algorithms. Then the optimal 1.5-competitive algorithm
LMM is presented and analysed in the next subsections.
3.1 The Lower Bound
By applying the standard argument of an adversary strategy, we will show the following
general lower bound:
Theorem 1
Every deterministic online algorithm A for the ORSM problem has a competitive ratio of
at least 1:5.
Proof. The adversary strategy starts with the following input structure:
@
@
@
@ @

Figure

1: Situation at time 2.
A can react to this input at time in three different ways:
Case 1: A puts the edge to the online matching MA . In the next step the adversary
presents edge g.
@
@
@
@ @
@
@
@
@ @
@
@
@
@ @

Figure

2: situation at time
A is not able to use the serving interval s 3 . Therefore, jMA j - 2 whereas the optimal
solution gives jM OPT
Case 2: A puts the edge to the online matching MA . In the next step the adversary
presents edge g.
@
@
@
@ @

Figure

3: situation at time
A cannot use s 4 . Again jMA j - 2 and the optimal matching results in jM OPT
Case 3: A decides not to match s 2 .
The adversary will present the input of Case 1 (the input of Case 2 would work as
well) and jMA
@
@
@
@ @
@
@
@
@ @

Figure

4: situation at time
This strategy can be infinitely repeated every four time steps and this fact shows the ratio
3:
Theorem 1
3.2 The Algorithm LMM
At a time step i the graph G representing the input of an online algorithm is known
up to request vertex r i . More precisely, we know the subgraph of G induced by the set
[S. Due to the irreversible decisions of the former time steps
all previous server vertices matched request vertices r k
cannot be rearranged anymore (M i is the online matching up to time
have a vertex induced bipartite subgraph of G:
~
Our online algorithm is called 'Local Maximum Matching' (LMM) because it constructs a
maximum matching on every local subgraph B i (denoted by M(B i )). The exact function
of LMM follows:
1:
2: loop
3:
4: read input of time i and build up B i
5: construct a maximum matching M(B i ) on
start with all matching edges of M(B i\Gamma1 ) which are edges in B
look for an augmenting path which starts at vertex r i and do the
augmentation when found 5
7: if s i
8: add the matching edge of s i to the online matching MLMM
9: else if s i is not isolated in B i then fall neighbours of s i are matched in M(B i )g
10: add an arbitrary edge fs to the matching MLMM and delete the
matching edge of r in M(B i )
12: end loop
Line 10 of this algorithm is essential and prefers a matching which includes the current
vertex s i . Now we will analyse the performance of LMM.
5 due to the maximum cardinality of M(B augmenting path must have r i on one end
3.3 The Upper Bound
At first, two invariants of LMM will be formalized in lemmata.
After a request vertex r i has been matched in B i for the first time, it is in all following
maximum matchings r i
to the time step where its current matching
edge is added to MLMM and so r i
holds in the end.
Proof. In line 5 of LMM at time j the matching edge of a previous matched request
vertex
copied to M(B j ) and an augmentation in line 6 can
change r's matching edge but r ffi
In line 10 the matching edge of a vertex
but after this step r ffi
Lemma 3
If s i is not isolated in B i , then s i
holds.
The lemma follows directly from line 7 to 11 of LMM. Applying these two invariants we
can prove the upper bound now.
Theorem 4
LMM is 1.5-competitive.
Proof. We will show that no online matching MLMM can be increased by augmenting
paths of length one or three. Therefore, shortest augmenting paths for MLMM must have a
length of five.
This fact immediately results in the theorem because by performing the augmentation, two
matching edges out of MLMM become three edges in M OPT . Longer augmenting paths have
a lower ratio and matching edges outside such paths decrease the overall ratio as well.
Let us fix an arbitrary input graph G I and a maximum matching M
can compare M OPT with the matching MLMM constructed by LMM on G I . The symmetric
difference M OPT \Phi MLMM defines a set of disjoint augmenting paths for MLMM (for more
details see [Edm65]). The augmentation of all of these paths transforms MLMM to M OPT .
By contradiction, we will prove the non-existence of paths of length one and three in this
set.

Figure

5: Structure of augmenting paths of length one and three.
Case 1: augmenting path of length one fs
Vertex r a was never matched because r a
(reverse application of Lemma 2).
a g is in B i and this fact contradicts Lemma 3.
Case 2: augmenting path of length three and
r a was matched at time j only, which implies the edge fs was in B i . Then
Case 3: augmenting path of length three and i ? j:
At time j, request vertices r a ; r b
2 MLMM and so the whole path ffs
gg is in B j .
The case s i
contradicts the optimality of M(B j ) because the path is an
augmenting one. Therefore, at time j s i
must hold, i. e. there exists a
request vertex r c with fr c ; s i Later at time k (j
deletes the matching edge fr c ; s i g and adds fs to MLMM .
Due to the definition of the ORSM problem, both edges are known
at time j. Now the above argument about s i can be recursively applied to s k and
due to the finite structure of B i , this fact contradicts the existence of an augmenting
path of length three in MLMM .
Theorem 4
4 The Online Request Server Weighted Matching
Problem
Like in section 3, we present a general lower bound for the wORSM problem first. Then
the algorithm wLMM is given and analysed. Unfortunately this algorithm cannot achieve
the lower bound and so we suggest the algorithm PHI at the end of this section.
4.1 The Lower Bound
Let OE :=
5+1- 1:618034 be the golden ratio.
Theorem 5
Every deterministic online algorithm A for the wORSM problem has a competitive ratio of
at least
Proof.
The adversary strategy starts with input edges and their weights are
as you can see in Fig. 6.
@
@
@
@ @

Figure

Situation at time
A can react to this input in two ways:
Case 1: A adds edge to the weighted online matching MA . Then the adversary
does not presents any new edge incident to s 2 . So jMA holds.
Case 2: A does not change the online matching MA . Then the adversary presents edge
with weight w(fr
@
@
@
@ @

Figure

7: Situation at time
Now A is able to construct a matching with weight jMA j - OE only, whereas it holds
OE. The ratio of these two values is:
OE
Every two time steps the adversary can repeat this strategy up to infinity and this fact
shows the lower bound of the competitive ratio of
5+1. \Xi Theorem 5
4.2 The Algorithm wLMM
The algorithm wLMM works very similarly to LMM. Of course, wLMM determines a maximum
weighted matching on the local bipartite graph B i . Furthermore, the algorithm works
without the special preference of the vertex s i . Later, on page 30, we will explain why a
special treatment of s i , in the way LMM does, cannot increase the performance of wLMM.
Our investigation will indicate the problems arising from this fact. A formal description of
wLMM follows:
1:
2: loop
3:
4: read input of time step i and build up B i
5: construct a maximum weighted matching M(B i
7: add the matching edge of s i to the online weighted matching MLMM
8: end if
9: end loop
4.3 The Performance of wLMM
In this section we present a tight analysis of wLMM being 2-competitive. At first we exhibit
a lower bound of wLMM which establishes the fact that wLMM is not able to achieve the
lower bound of theorem 5.
The Lower Bound
Theorem 6
The online algorithm wLMM has a competitive ratio of at least 2.
Proof. An adversary presents the input w(fr
and in the next time step w(fr
@
@
@
@ @

Figure

8: Input structure that is used by the adversary
The algorithm wLMM determines the online matching which has a
weight of jMwLMM ". The optimal solution is with
weight jM OPT 2. Consequently,
and the limit for
Theorem 6
The Upper Bound
Firstly, we repeat a few definitions and give new ones which will be used extensively in the
following proofs. Most of the notations are similar and comparable to [BR93], whereas one
different notation is introduced. By the use of this notation, we aim to make the formulae
more accessible.
Definitions and Notations
is the bipartite, weighted graph of the wORSM problem with the
weight function w
M i is the online matching which is calculated up to step i by wLMM.
M(B) is a maximum weighted matching of a bipartite graph B.
is the overall weight of a maximum
weighted matching of B.
is the local bipartite graph of step i which consists of all known and not
matched request vertices R i ae R with
non-passed
server vertices edges between this two sets
(R i
Both notations above can be combined. We use indexed r's and s's to denote vertices of
R and S, so the partition where these vertices come from is unambiguous. Additionally,
we employ a list of inserted or deleted vertices when necessary. A typical usage of this
notation is B i
which describes the vertex induced subgraph Gj R i
Let M(B i ) be a maximum weighted matching of B i and let M(B i
!s ) be such a matching
of B i after removing the vertex s. The symmetric difference of these two sets results in
a path P :=
!s ). It is an augmenting path 6 in B i with respect to the
matching M(B i
!s ). We will use notation P for the set of edges as defined above and
6 this path can be empty
for a graph is the defined set of edges, and
set V P gathers all the incident vertices. With this definition, we define the value of the
corresponding server vertex as:
It is obvious that fi i
!s ) as above. Sometimes we call fi i (s) the weight of path P because this value is
added to the overall matching when augmenting P .
Next we define the global potential function:
At last the following abbreviated notations will be used for an expression f :
f jv is the value of f in step i with
\Deltaf jv is the difference of the value of expression f before and after processing vertex v.
Now some important properties of weighted augmenting paths which corresponds to fi(v)
are listed. In this context we can relax the restriction to bipartite graphs. All above
mentioned definitions applies to simple, undirected, weighted graphs.
Lemma 7
be a simple, undirected, weighted graph. Then it holds:
Proof. G !v is a subgraph of G and both M(G) and M(G !v ) are optimal. So it
holds
Lemma 8
Every subpath P b which arises from P by deleting an even number of edges from the
start vertex v and which starts itself by vertex b is optimally matched by the matching
of P , i. e. M(P b
Every subpath P c which arises from P by deleting an odd number of edges from the
start vertex v and which starts itself by vertex c is optimally matched by the matching
of P !v , i. e. M(P c
v a b c
a b c
s q q q
c

Figure

9: Sketch of the paths described in Lemma 8 including their optimal matchings.
Proof. We prove statement (I) by contradiction. Assume M(P b is not optimal:
The matching edge of b is in P b , fb; cg 2 M(P ) and fb; cg 2 P b because fv; ag 2 M(P )
and b is in a distance of even edges away from v. Path P can be divided into two subpaths
at vertex b and it holds:
Then the above assumption implies:
which contradicts the optimality of M(P
In the same way statement (II) is proven. The line of argumentation is about P !v and
instead. Notice that in M(P !v ) the matching and non-matching edges are exchanged
in comparison to M(P ) by definition of P . \Xi Lemma 8
Lemma 9
path P and subpaths P b and P c be defined as in Lemma 8. The value fi(v) can be
expressed from vertex b or c onwards by fi(b) or fi(c) in the following way:
Matching M(P ) can be divided into M(P nP b ) and M(P b ) by Lemma 8. In the same
way M(P !v ) can be divided into M((P n P b ) !v
Matching M(P ) can be divided into M((P n P c
!c ) by Lemma 8.
In the same way M(P !v ) can be divided into M((P n P c
it holds:
fi(c)
Proof. The Lemma follows from Lemma 9 part (II) with the subpath P c starts with
vertex u. Then m((P n P u is the empty graph with
and the application of Lemma 7 (fi(u) - 0) completes the proof.
Lemma 11
be a simple, undirected, weighted graph, v 2 V , and let fi(v) correspond
to a path P of even length. When a manipulation of G increases the length of P , the value
of fi(v) will never decrease, i. e.
Proof. Suppose b to be the last vertex of path P and P b be the extension of P . We can
use Lemma 9 part (I) because P has an even length. We then achieve:
Then
and by applying of Lemma 7:
Lemma 12
be a simple, undirected, weighted graph, v 2 V , and let fi(v) correspond to
a path P . When a manipulation on G decreases the length of P such that fi + (v) corresponds
to a path of odd length, then the value of fi(v) will never decrease, i. e.
Proof. Suppose c to be the last vertex of the reduced path (corresponding to fi
and P c
!c be the shortening itself. We can use Lemma 9 part (II) because P + has an odd
length, and we achieve:
Then
and by applying of Lemma 7:
Now we are able to give two key lemmata, which are needed to prove the upper bound.
The statements of these lemmata are the same as in [BR93] and there are called identically.
The line of argumentation in our proof follows E. Bernstein's and S. Rajagopalan's proof,
too.
The Key Lemmata and the Proof
Lemma 13 (Stability Lemma)
The value of a server vertex never decreases, i. e.
\Deltafi
Proof. When wLMM is running the following changes on the local graph B can happen:
Case 1 'matching': A matching edge added to the online matching,
This edge including its both vertices is removed from
Case 2 'non-matching': The current server vertex s i is not matched (s i
is removed from
This can happen when the weights of edges incident to s i are too small.
Case 3 'input': A new request vertex r i is added to
We will show that in all three cases the value fi(s) of an arbitrary server vertex s 2 S i will
not decrease. Let Q be the path corresponding to fi(s). Whenever Q is not affected by
one of the above cases, it holds: fi Henceforth, it is sufficient
to assume a modification in the structure of Q.
Case 1 shortened by removing one of its matching edges.
This removal includes all adjacent non-matching edges. Hence, the shortened path Q has
a matching edge on both of its ends and therefore it is of odd length. An application of
Lemma 12 gives \Deltafi
Case
path Q is shortened by removing its last vertex s i (all other
vertices of Q are matched in M(B i )). Again the removing of s i removes all incident edges
has two matching edges on its ends. So it is of odd length, and by Lemma 12 it
holds \Deltafi
first we focus on the possibility that the new request vertex is not matched,
However, such a situation does not change any path Q and therefore it holds
The reason is that r i could be the last, non-matched vertex of Q
only. Then Q has an even length. By definition, Q starts with a server vertex s 2 S i
which implies that all request vertices are situated in an odd distance to s. This fact
implies a contradiction.
Henceforth, we assume that r i is matched to a server vertex s j in the enlarged graph
was augmented which is described
exactly by M(B /r i
We define the weight of path P just as the value of a
server vertex
Now we have to distinguish whether s j was matched in M(B) before.
Case 3.a: s j
M(B). No path Q of odd length could become extended because these
paths have two matched end vertices. This is a contradiction to the assumption of this
case. If Q is of even length and has been extended, then Lemma 11 can be applied and
this results in \Deltafi
Case 3.b: s j
M(B). The following statements are implicated by the preconditions of
this case:
ffl P is an augmenting path of length ? 1 because s j was matched before.
ffl There exists a vertex v which is the first common vertex of path P and Q. At that
point, the paths meet first time with respect to their start vertices.
From this facts we can conclude:
would be matched to a vertex of Q which is not in P and to
another vertex of P . This is a contradiction.
7 Note: the definition of fi(s) was made for server vertices s 2 S only
s

Figure

10: Situation just before P is augmented.
ffl From vertex v onwards, paths P and Q are identical. Lemma 9 part (I) gives the
reason for this statement 8 , since fi(v) is the same for both paths.
Lemma 9 part (I) allows us to express fi(s) by fi(v). Due to the fact that no matching
edge is changed between s and v on path Q (see also Fig. 10) it holds:
Hence, it is sufficient to investigate \Deltafi (v). We can observe that v is matched to the
farther request vertex with respect to r i , before path P is augmented. This augmentation
exchanges all matching and non-matching edges on P . Then, v is matched to the request
vertex that is closer to r i and the path corresponding to fi + (v) has the 'opposite direction',
i. e. it starts at vertex v and ends at vertex u where u is situated between v and r i .
\Gamma! fi(v)
This vertex u has to be a request vertex, u 2 R i . Otherwise it would be matched in M(P )
outside the path described by fi + (v) which is a contradiction to the definition of fi
Vertex u and r i can be identical.
8 Note: A very careful inspection shows the possibility that this statement does not necessarily hold.
On the one hand fi(v) is an optimized value and it is equal in P and Q. On the other hand, there can exist
two different paths P tail
and Q tail
which start at vertex v and have the same value fi(v). Without loss of
generality, select the maximum matchings which define P such that Q tail
is the part of P form v onward.
It is obvious that these matchings exist and that we get proper definitions for P , fi(s j ), and
The definition of \Deltafi (v) gives:
Substituting this claim in equation (2):
and by Lemma 7 fi 0 (u) - 0, which completes the proof. Lemma 7 can be applied here
because it holds for the value fi(\Delta) of a vertex in a general, simple, undirected graph.
Proof of the claim:
On the left hand side, the vertex v is removed out of path P in both terms. Hence, P is
divided into two subpaths
is situated in P 1 .
The maximum weighted matching of P 2 is the same in M(P !v ) and M(P !r i ;v ), and it
has no influence on the difference m(P !v
Let P r be a subpath between r i and u, and let P u be the subpath of P from u onward.
z -
By definition of fi 0 (r i ) and Lemma 8:
To establish the statement m(P r
sufficient to
have a look at P 1 . When P was augmented (from M(P !r i ) to M(P matching and
non-matching edges were exchanged. After the removal of vertex v, path P 1 is augmented,
and again all matching and non-matching edges are exchanged in the subpath between v
and u which is described by fi (v). In this subpath we have the same situation as before
when r i had been inserted. Then the difference between M(P 1 ) and M(P 1
be found in P r (to be more precise: M(P 1
From the above equation, we get:
Lemma 14 (Pay-Off - Lemma)
During a run of wLMM holds:
Before proving the lemma we would like to present an interpretation of the formulae.
Statement (I) establishes the fact that the potential function \Phi increases by at least the
value of fi(s) when the server vertex s is processed. Statement (II) ensures the choice of
the heaviest augmenting path when a request vertex r is inserted and matched. The left
hand side of this inequation is the weight of the selected augmenting path whereas the
right hand side describes the weight of all possible augmenting paths that start in vertex
r (see Lemma 9 part (II)).
Proof. For simplicity of notation the index i is omitted.
and
Substituting the above equations into the definition of \Delta\Phi js :
\Delta\Phi
and by Lemma 10:
\Delta\Phi
Case 2: 'non-matching', s
and
Substituting the above equations into the definition of \Delta\Phi js :
\Delta\Phi
and together we have:
\Delta\Phi
(proof by contradiction)
Let r 2 R and m(B /r ) be the overall weight of an optimal matching of B including vertex
r.
Assumption: 9 s 2 S i such that
The matching M is not changed by the insertion of r and we have:
\Delta\Phi
Substituting the assumption by this equation:
\Delta\Phi
The term is the weight of a matching in graph B /r because both
vertices r and s are not in B !s . This contradicts the assumed optimality of m(B /r )
and the lemma is proven. \Xi Lemma 14
Theorem 15
The deterministic online algorithm wLMM for the wORSM problem is 2-competitive.
Proof. For all request vertices r 2 R we get from Lemma 14 part (II):
while the definition of the wORSM problem ensures that r is processed before s :
We get from Lemma 14 part (I) for all server vertices s 2 S:
and by the use of Lemma 13, since s is processed after r :
The sum of equations (4), (5) and (6) is
Then, for an arbitrary matching MG of G holds:
\Delta\Phi js -
Hence, we get for
final - jM OPT j
and from the definition of \Phi, and the fact that B final = ?, it follows:
which shows the 2-competitiveness of wLMM. \Xi Theorem 15
A Comment on the wLMM-Algorithm
Why does wLMM not prefer the current server vertex s i in the online matching, like LMM
does? The answer to that question is a very short one: It does not help anyway.
Suppose an algorithm wLMM   which prefers the current server vertex in the way like LMM
does. Furthermore, assume an input graph such that MwLMM   6= MwLMM . Let
s i be the first vertex where wLMM   makes a different decision than wLMM (s i
and s i
decreasing all weights of edges incident to s i by ", wLMM   will
behave like wLMM on s i . With the help of this trick, we can construct an input graph
calculates the same matching as wLMM does on input
G. The difference in the weights of the resulting online matchings jMwLMM   j and jMwLMM j
is small and disappears for "
Possibly, the next section shows a way out.
4.4 The Algorithm PHI
The algorithm wLMM implements a special greedy strategy. From its current point of view,
it takes the maximal, additional weight for the online matching. Theorem 6 shows a situation
where this strategy is not very clever. With regard to theorem 5 (construction of the
general lower bound) and theorem 6 we suppose that there is an algorithmic improvement.
Using the current vertex s i in the online matching M , and therefore removing a vertex r
out of B i simultaneously, may be more valuable than the originated loss in M(B i ). This
observation leads us to suggest another online algorithm for the wORSM problem. It works
similarly to wLMM but after computing the local maximum weighted matching M(B i ), it
checks the vertex s i . Whenever s i
holds, the weights of all edges of B i incident
to s i will be increased by the factor
5+1. This new local bipartite graph is called
Now the algorithm determines M(B OE
matching edge is added to the online matching M . The new online algorithm is called PHI
and a formal description follows:
1:
2: loop
3:
4: read input of time i and build up B i
5: construct a maximum weighted matching M(B i
7: construct B OE
fincrease the weight of every edge of B i incident to s i by factor
8: calculate the maximum weighted matching M(B OE
9: end if
11: add the matching edge of s i to the online weighted matching M PHI
12: end if
13: end loop
A problem still unsolved is the performance analysis of PHI. It seems as if a modification
of the technique, that is used in the proof of theorem 15 does not work. It is likely that
), then the algorithm does not need to calculate B OE
) and to
test s i
these facts (the necessity of a modified algorithm like PHI and a new technique to analyse
it) also explain the gap in the analysis of the roommates problem in [BR93].
It is worth noting that the algorithm LMM is a special implementation of PHI for unit edge
weights. The increasing of unit weights of s i -edges by a factor of OE is equivalent to the
simple preference of an edge incident to s i at time step i.
5 Open Problems
In the end of the last subsection we presented the most urgent research task: To close
the gap between the lower and upper bound of the wORSM problem (Theorem 5 and
Theorem 15). If we achieve this aim, the roommates problem (weighted version) of [BR93]
should be revisited.
A completely different research task deals with the ORSM problem (unweighted version).
Here, the performance on inputs of strong, pre-determined structures is of interest. Finally,
we would like to model a set of parallel, homogeneous resources and requests with deadlines.
First results have been already proven. It turned out that dependent on the concrete model:
ffl lower competitive ratios are achievable,
ffl the algorithm LMM is not optimal anymore,
ffl different arguments to prove upper bounds are necessary.
These investigations are not completed by now but they will be presented in a later publication



--R

The competitiveness of on-line assignments
On the power of randomization in on-line algorithms
Online Computation and Competitive Analysis.
The roommates problem: Online matching on general graphs.

Network flow and testing graph connectivity.
Online computation.


Online weighted matching.
An optimal deterministic algorithm for online b-matching
Online matching with blocked input.
An optimal algorithm for on-line bipartite matching

Amortized efficiency of list update and paging rules.
--TR
An optimal algorithm for on-line bipartite matching
Online computation
Online computation and competitive analysis
Simple competitive request scheduling strategies
Online Scheduling of Continuous Media Streams
On-line Network Optimization Problems
On-line Scheduling
The Roommates Problem
competitive analysis;online scheduling;online bipontite matching