The Online Transportation Problem.
We study the online transportation problem under the assumption that the adversary has only half as many servers at each site as the online algorithm. We show that the GREEDY algorithm is $\Theta( {\rm min}(m, \lg C))$-competitive under this assumption, where m is the number of server sites and C is the total number of servers. We then present an algorithm BALANCE, which is a simple modification of the GREEDY algorithm, that is, O(1)-competitive under this assumption.
Introduction
We consider the natural online version of the well-known transportation problem
[2, 5]. The initial setting consists of a collection of server
sites in a metric space M. Each server site s j has a positive integral capacity c j .
The online algorithm A sees over time a sequence ng of requests for
service, with each request being a point in M. In response to the request r i , A
must select a site s oe(i) to service r i . The cost for this assignment is the distance
in the metric space between s oe(i) and r i . Each site s j can service at
most c j requests. The dilemma faced by the online algorithm A is that, at the
time of the request r i , A is not aware of the location of the future requests. The
goal for the online algorithm is to minimize 1
cost
to service the requests. Note that this is equivalent to minimizing the total cost
For concreteness, consider the following two examples of online transportation
problems. In the fire station problem, the site s j is a fire station that
contains c j fire crews. Each request is a fire that must be handled by a fire crew.
The problem is to assign the crews to the fire so as to minimize the average
distance traveled to get to a fire. In the school assignment problem, the site s j
is a school that can has a capacity of c j students. Each request is a new student
who moves into the school district. The problem is to assign the children to a
kalyan@cs.pitt.edu, Computer Science Dept., University of Pittsburgh, Pittsburgh, PA
15260, Supported in part by NSF under grant CCR-9202158.
y kirk@cs.pitt.edu, Computer Science Dept., University of Pittsburgh, Pittsburgh, PA 15260,
Supported in part by NSF under grant CCR-9209283.
school so as to minimize the average distance traveled by the children to reach
their schools.
The standard measure of "goodness" of an online algorithm is the competitive
ratio. For the online transportation problem, the competitive ratio for an online
algorithm A is the supremum over all possible instances I, of A(I)=OPT (I),
where A(I) is the total cost of the assignment made by A, and OPT (I) is the
total cost of the minimum cost assignment for instance I. The standard way
to interpret the competitive ratio is as a payoff of a game played by the online
algorithm A against an all powerful adversary that specifies the requests, and
services them in the optimal way. Note that the instance I specifies the metric
space as well as the values of each s j , c j , and r i .
In [1, 3] the online assignment problem, a special case of online transportation
in which each capacity c In [1], it was shown that the
competitive ratio of the intuitively appealing greedy algorithm, which assigns
the nearest available server site to the new request, has a competitive ratio of
In [1, 3], it was shown that the optimal deterministic competitive ratio
is 1. The algorithm that achieves this competitive ratio requires a shortest
augmenting path computation for each request. These results illustrate some
shortfalls of using competitive analysis, namely:
ffl The achievable competitive ratios often grow quickly with input size, and
would seem to overly pessimistic for "normal" inputs.
ffl The algorithm that achieves the optimal competitive ratio is often unnecessarily
complicated for "normal" inputs.
ffl The poor competitive ratio of an intuitive greedy algorithm may not reflect
the fact that it may perform reasonably well on "normal" inputs.
In situations where competitive analysis suffers such shortcomings, it is important
to find alternate ways to to identify online algorithms that would work
well in practice. In this paper, we adopt a modified version of competitive analysis
that we call the weak adversary model. Generally speaking, in this model
the adversary is given slightly less resources than the online algorithm. The
intuition is that for "normal" inputs, one might expect that the performance of
an offline algorithm would not degrade significantly if its resources were slightly
reduced. Hence, if we can prove that an online algorithm is competitive against
an adversary with slightly less resources, then one might argue that the online
algorithm will be competitive against an equivalently equipped offline algorithm
on "normal" inputs. One can also view this weakening of adversary as measuring
the additional resources required by the online algorithm to offset the decrease
in performance due to the online nature of the problem.
In the case of the transportation problem we compare the online algorithm
with c i servers at s i to an offline line algorithm with a servers at s i
(we assume that c i is even). Given an instance I of the online transportation
problem with n requests,
I 0 be the same instance with each
capacity c i replaced by a i . We then say the halfopt-competitive ratio of an online
algorithm A is the supremum over all instances I, with
of the ratio A(I)=OPT (I 0 ). We assume that the online algorithm has twice as
many servers as the adversary because this is the least advantage that we can
give to the online algorithm without annulling our analysis techniques.
In this paper we present the following results. In section 3, we show that
the halfopt-competitive ratio of the greedy algorithm is \Theta(min(m; log C)), where
is the sum of the capacities. If the server capacity of each site is
constant, then the halfopt-competitive ratio is logarithmic in m, a significant
improvement over the exponential bound on the traditional competitive ratio.
In section 4, we describe the algorithm Balance, which is a simple modification
of the greedy algorithm, and has a halfopt-competitive ratio that is O(1). Recall
that the traditional competitive ratio of every deterministic online algorithm is
m).
We now summarize related results. The weakened adversary model was introduced
in [6] in the context of studying paging. This model has also been used
to study variants of the k-server problem, a generalization of the paging problem
(see for example [8]). References to other other suggested variants of competitive
analysis can be found in [4]. Further ancillary results on online assignment,
which are not directly related to the results in this paper, can be found in [1].
In [7], the average competitive ratio for the greedy algorithm in the online assignment
problem is studied under the assumption that the metric space is the
Euclidean plane and the points are uniformly distributed in a unit square. The
offline transportation problem can be solved in polynomial-time[2, 5].
Preliminaries
In this section we introduce some definitions, facts, and concepts that are common
to the remaining sections. We generally begin by assuming the simplifying
condition that the online capacity c i of each server site is two. We will think
of s i as containing two online servers s 1
i that move to service requests.
We also think of s i as containing one adversary server s a
i . We assume, without
loss of generality, that the adversary services request r i with s a
i . We use s oe(i) to
denote the site that the online algorithm uses to service request r i . We define
a weighted bipartite graph E), which we call the response graph,
by including an online edge (r and an adversary edge (r
request r i . The weight of each edge (r G is the distance d(r
the r i and s j in the underlying metric space. In figure 1, the online edges are
the solid edges, the adversary edges are the dashed edges, the server sites are
the filled circles, and the requests are the question marks. The notation shown
in figure 1 will be used throughout this paper.
request vertex that is in a cycle in G. Let T be the connected
component of G \Gamma (s contains r i . Then T is a tree.
Proof: Consider a breadth first search of T starting from r i . Such a search
divides T into levels L where the vertices in level L k are k hops from
r a
s a s b
r c
r
s
r r
s
s
d
d
e
e
f
f

Figure

1: An Example Connected Component of the Response Graph
r i . The vertices in the odd levels are server vertices, and the vertices in even
levels are request vertices. Edges that go from an even level to an odd level are
adversary edges, and edges that go from an odd level to an even level are online
edges. Assume to reach a contradiction that C is a cycle in T . Let y be the
vertex in C that is in the highest level L c (i.e., largest c), and let x and z be the
two vertices adjacent to y in C. Note that it may be the case that x = z. Now
it must be the case that x and z are in L c\Gamma1 or we would get a contradiction to
one of the bipartitieness of G, the definition of x, or the definitions of the levels.
If c is odd, then we get a contradiction to the fact that the adversary has only
one server per site. If c is even, we get a contradiction to the fact that the online
algorithm only uses one server to service each request.
Let T be a tree as described in lemma 1. If we root the tree T at r i then T
has the following structure. For each request r j 2 T , the one child of r j is s j . If
r j is not the root, then the server site s oe(j) is the parent of r j in T . The leaves of
are server sites with no incident online edges. We denote the total cost of the
adversary edges in a tree T by OPT (T ), that is, OPT
Analogously, we define ON
Note that ON (T ) includes
the cost of the online edge incident to the root of T , even though this edge is not
in T . For a vertex x 2 T , we define the leaf distance ld(x) to be the minimum
over all leaves s j in T of the distance between x and s j . If a server at site s j
serviced the root r i of T , then ld(s x is a node in T , we
define T (x) to the the subtree of T rooted at x.
In this paper, log means the logarithm base 2.
3 Analysis of the Greedy Algorithm
We begin with the upper bound on the competitive ratio for the algorithm
Greedy, which uses the nearest available server to service each request. We
first assume that the online capacity of each server site is two, and then show
how to extend the proof to the general case.
Theorem 2 The halfopt-competitive ratio of Greedy for online transportation,
with and two online servers per site, is at most 2 log m.
In order to prove this theorem, we will divide the response graph G into
edge disjoint rooted trees, T l . For each such tree, we will establish the
competitive bound independently.
Our construction yields trees (T j 's) that satisfy the following tree invariants:
1. Each nonleaf server site s i in T j has two incident online edges in T j .
2. Each leaf of T j is a server site that had an unused server at the time of
each request in T j .
Using the following iterative procedure to construct the trees.
Tree Construction Procedure: Assume that trees T
constructed. We explain how to construct T j in our next iteration. During this
construction we will modify G. The root of T j is the most latest request r ff(j)
not included in a previous tree T . The online edge incident to r ff(j)
is removed from G. Let L be the collection of server vertices s i such that s i is
reachable from r ff(j) , and s i currently has at most one incident online edge in G.
Note that an s i 2 L might have originally had two incident online edges if one
or both of these edge lead to the root of one of the trees T
T j be the edges on paths in G from r ff(j) to the server vertices in L. Note that
by lemma 1 there is a unique path from r ff(j) to each vertex in L. It is not hard
to see that T j satisfies the tree invariants. The edges and request vertices in
are then removed from G, and we proceed to our next iteration to construct
contains edges.
We now fix a particular tree, say simplicity drop the j
superscript.
Lemma 3 For each request r
Proof: The proof is by induction on the number k of request nodes in the induced
tree T (r i ). If then the child s i of r i is a leaf, and T (r i ) consists of one
adversary edge (r
by the definition of Greedy.
Now suppose k ? 1. If s i is not a leaf then it has two children in T (r i ),
say r a and r b (see figure 1). By induction, it must be the case that ld(r a
OPT (T (r a )), d(s
OPT (T (r b )). Therefore by induction and the triangle inequality,
The fact that d(s since Greedy would
only assign s oe(i) to r i if d(s
Lemma 4 Let r i be a request in T , and let k be the number of request vertices in
Proof: The proof is by induction on k. Observe that according to our tree
construction, each server node has either two children or none. Therefore, k
must be odd.
For
by the definition of Greedy.
Now consider the case 3. Let the two children of s i in T (r i ) be r a and
r b . Note that
ON (T (r
and that
By the definition of Greedy, d(s
lemma 3, d(s Hence, by substitution,
ON (T (r i
Now consider the case k ? 3. Once again let the two children of s i in T (r i )
be r a and r b . Notice that ON (T (r
By equation 1,
Hence,
ON (T (r i
loss of generality, that OPT (T (r a
y be the number of request nodes in T (r a ). We now break the proof into cases.
In the first case, we assume that both T (r a ) and T (r b ) consist of more than
one request vertex. Hence, 3 - y 4. By induction ON (T (r a
and ON (T (r b Hence, by substituting into equation
2 we get
ON (T (r i
in order to show ON (T (r i
OPT (T (r i )) it is sufficient to show
2x log y
In turn it is sufficient to show that
x log y
Let f(x; x be the left hand side of this
inequality. Notice that f(x; y) is linear in x. Hence the maximum of f(x; y)
must occur at the boundary, that is, at the point or the point
Inequality 3 follows immediately for we have to find the
value of y that maximizes f(w=2; 1). The
derivative of f(w=2; y) with respect to y is w
y
k\Gamma1\Gammay )). Hence, one can
see that the maximum f(w=2; y) occurs at 1)=2. We now must show
that
which by algebraic simplification is equivalent to log(k \Gamma 1) - log k.
We now consider the case that T (r a ) contains only one request. So
By induction ON (T (r a
by substituting into equation 2 we get
ON (T (r i
In order to show that ON (T (r i is sufficient to show
Since the left hand side is linear in x, we need only consider
The case immediately. If are left with showing
k. This is equivalent to log(2
log k, or
which one can verify holds for k - 3.
We now consider the case that T (r b ) contains only one request. So 2.
By induction ON (T (r a
by substituting into equation 2 we get
ON (T (r i
In order to show that ON (T (r i is sufficient to show
that
Since the left hand side is linear in x, one need only verify that the inequality
holds at the boundaries
Proof: (of Theorem 2.) Applying lemma 4 to each tree T i , we get the desired
result.
We now extend the result to the case that the online capacities are larger
than two. Recall that
is the total online capacity.
Theorem 5 The halfopt-competitive ratio of Greedy for online transportation is
O(min(m; log C)).
Proof: The upper bound of O(log C) is immediate by theorem 2 if we conceptually
split a server site with c i online servers into c i =2 sites with 2 arbitrary
online servers and 1 arbitrary adversary server.
To see the O(m) bound we need to be more careful about how we split the
server sites up. Assume that the tree construction procedure just constructed a
tree T k . We perform some pruning of sT k , if necessary, before we proceed to
construct T k+1 . If no root-to-leaf path in T k passes through two server sites that
are at the same location, then the number of vertices in T k is O(2 m ). Hence,
the O(m) bound follows from lemma 4.
If T k contains root-to-leaf paths that pass through two server sites that are
at the same location, we show how to modify T k to remove such paths. Assume
that T k contains a root-to-leaf path that first passes through s i and then passes
through s j , where s i and s j are at the same location. We modify T k by making
server vertex s j the child of r i in T k . See figure 2. Note that may remove edges
and vertices originally below s i from T k . We repeat this process until T k has no
root to leaf path passing through two server sites at the same location. Notice
that the resulting tree T k still satisfies the tree invariants. Now we start the
construction of T k+1 .

Figure

2: The original T k on the left, and the new T k on the right
We now prove an asymptotically matching lower bound for the halfopt-
competitive ratio for Greedy.
Theorem 6 The halfopt-competitive ratio of Greedy for the transportation problem
is
\Omega\Gamma/15 (m; log C)).
Proof: Assume without loss of generality that C). We embed m
server sites on the real line. The server site s 1 is located at the point \Gamma1. The
server site s i m) is located at 2 1. The online algorithm has
servers at s i , while the adversary has a servers at s i . Thus
the online algorithm has a total of servers, while the adversary has
a total of servers. The requests occur in m batches. The first batch
consists of 2 m\Gamma1 requests at the point 0. The ith batch (2 - i - m) contains
requests that occur at 2 the location of s i . Greedy responds to
batch m) by answering each request in batch i with a server at site s i+1 ,
thus depleting site s i+1 . Greedy responds to the mth batch by moving one
server from s 1 . Thus the total online cost is m2 . By using the servers in s i
to handle batch i (1 - i - m) it is possible to obtain a total cost of 2
4 The Algorithm Balance
In this section we present an algorithm, Balance, with a halfopt-competitive
ratio of O(1).
Algorithm Balance: At each site s h we classify half of the servers as primary
and half of the servers as secondary. Let c ? 5
2 be some constant. Define
the pseudo-distance from a request r i to a primary server at site s j to be d(s
and the pseudo-distance from r i to a secondary server at site s j to be c \Delta d(s
Balance services each request r i with an arbitrary server with minimal pseudo-distance
from r i .
Our goal is now to show that the halfopt-competitive ratio of Balance
for online transportation, with two online servers per site, is O(1). We first
break the response graph G into disjoint trees. Let C l be the connected
components of the response graph G. By lemma 1 each connected component of
the response graph contains a unique cycle. Let r ff(i) be the most recent request
in the cycle in C i . Let T j be the tree that is C j minus the online edge incident
to r ff(j) , and we set the root of T j to be r ff(i) . Each such tree T j satisfies the
following two tree invariants:
1. Each nonleaf server site s incident online edge in T ,
had the secondary server available just before the time of each request
2. Each leaf of T j is a server site s i that had both of its servers available just
before the time of each request in T j .
We now fix a particular tree, say simplicity drop the superscript
j. In order to show that the halfopt-competitive ratio of Balance is
O(1) it is sufficient to show that ON (T
Definition 7 Let s i be a generic server site in T . We say that the primary server
child s a of s i is the server site that the adversary used to service the request serviced
by s 1
, and the secondary server child s b of s i is the server site that the adversary
used to service the request serviced by s 2
. The server parent s p of s i is the server
site used by Balance to service r i . The site s i is a double if it has two server
children, and otherwise s i is a single.
Lemma 8 If Balance uses a server at site s p to handle a request r
and
Proof: Observe that there is a path in T from r i to some leaf s k with total
length at most d(r
Balance didn't use s k to service r i . If s
by the triangle inequality. Now
Lemma 9 Assume that Balance uses a secondary server s 2
p to handle a request
that is not the root of T . Then
and
Proof: Observe that there is a path in T from r i to some leaf s k with total
length at most d(r
Balance didn't use the primary server at s k to service r i . Now
Fact 11 For all nonnegative reals x and y, and for all c ? 1,
Proof: Suppose 2x - (1 + 1=c)y. It suffices to show that min(2x; (1
shows that (1
On the other hand, suppose 1=c)y. It suffices to show that
c+1 x). Simple algebra shows that
Lemma 12 Assume that s i is a double server site with server children s a and s b .
Then
Proof: Note that ld(s i by lemma 8, and that ld(s i
9. The lemma then follows by fact 11.
local if either s i is a single, or one of s i 's server
children is a single. Otherwise, s i is global. For convenience, we call a request r i
local if s i is local. Otherwise r i is global. For a server site s i we use z(s p ) to denote
We now break the accounting of the online edges in T into cases. We first
show that for every local server s i , the cost for Balance to serve r i is O(z(s p )).
local r i
Further for each parent server s p of a local server s i
Proof: We break the proof into two cases. In the first case assume that s i is a
single. It must be the case that d(s Balance didn't use
a server at s i to handle r i . Hence,
single local s i
single local s i
Further
In the second case assume that s i is double, and one of s i 's server children
is a single. For simplicity assume that s a is a single; one can verify that the
following argument also holds if s b is a single. Since s a is a single we can apply
the analysis from the previous case to get that d(s
Balance serviced r i with a server at s p instead of the unused server at s a we
get that
Hence, by substitution,
Thus X
double local s i
double local s i
double local s i
Furthermore,
The result then follows.
Now we consider the online cost of servicing the global r i 's. Observe that by
lemma 8 it is the case that
global r i 2T
global r i 2T
global s i 2T
We now will show that
global s i 2T
Definition 15 Let s i be a global server site in T . We define S(s i ) to be the set of
global server sites in the subtree of T rooted at s i with the property that, for any
server site s j 2 S(s i ), there are no global server sites in the unique path from s i to
s j in T . We define LC(s i ) to be the sum of the cost of the offline edges
the subtree rooted at s i with the property that the unique path from s i to r j in T
does not pass through a global server site.
To give an alternative explanation of LC(s i ) consider pruning T at the global
server vertices, which results in a collection of trees rooted at global server
vertices. Then LC(s i ) is the total cost of the offline edges in the tree rooted at
Lemma 16 For any global server site s i ,
Proof: If the server children s a and s b of s i are both global then
Hence, the result follows in this case since fl -
Now assume that at least one server child, say s a , of s i is local. Note that s a
and s b must be a double, since s i is global. Further assume for the moment that
s b of s i is global. Let s c and s d be the two server children of s a . Then using
equation 5 we get that
In this case we continue to expand ld(s c ) and ld(s d ) using the general expansion
method described below. Now consider the case that both s a and s b are local.
Let s e and s f be the server children of s b . Then using equation 5 we get that
In this case we continue to expand ld(s c ), ld(s d ), ld(s e ) and ld(s f ) using the
general expansion method described below.
We now describe the general expansion method. We expand each ld(s j )
using equations 4 and 6. A term of the form ld(s j ) is expanded according to the
following rules:
1. If s j is a leaf in T then ld(s j ) is set to 0.
2. If s j has a local server child s k , then ld(s j ) is set to
which is valid by equation 6. Observe that since s k is local it will be
subsequently expanded.
3. If none of s j 's server children are local then ld(s j ) is set to 2(d(r
is an arbitrary server child of s k . This is valid by equation
4. Note that in this case the term ld(s k ) is not expanded again since
The that appear in this general expansion process are all included
in LC(s i ). Hence, we get
for some ff and fi. Since each offline edge appears in this general expansion at
most twice, and in each case the coefficient is at most 1), we can conclude
that ff - 1). Note that in rule 2, the coefficient in front of the ld(s j ) term
before the expansion is the same as the coefficient in front of the ld(s k ) term
after expansion. Since the coefficient in front of each ld term is fl 2 before the
application of any of the general expansion rules, and the only way that it can
change is by application of rule 3, which is a terminal expansion, each coefficient
on a ld(s j ) term when general expansion terminates is at most 2fl 2 . The result
then follows.
Lemma
global s i 2T
Proof: First observe that if s i and s j are two different global server sites, then
there is no common offline cost in the sums LC(s i ) and LC(s j ). As a consequence
we get X
global s i 2T
Therefore, it suffices to show that
global s i 2T
global s i 2T
Applying lemma 16 we have that
global s i 2T
global s i 2T
global s i 2T
we get that
global s i 2T
global s i 2T
Now substituting back, we get
global s i 2T
global s i 2T
The result then follows.
Theorem The halfopt-competitive ratio of Balance, with two online servers
per site, in the online transportation problem is
Proof: The total online cost is (c 2 +c+1)OPT (T ) from lemma 14, plus OPT (T ),
plus
We now assume an arbitrary number of online servers per site.
Theorem 19 The halfopt-competitive ratio of Greedy for the online transportation
problem is
Proof: This follows immediately by conceptually splitting each server site s i into
sites.
5 Conclusion
The most obvious avenue for further investigation is to determine the competitive
ratio in the weakened adversary model when the adversary's capacity is more
than half of the online capacity. It seems that some new techniques will be
needed in this case since the response graph no longer has the treelike property
from lemma 1 that was so critical in our proofs.



--R

"Online weighted matching"
Algorithms for Network Programming
"On-line algorithms for weighted matchings and stable marriages"
"Beyond competitive analysis"
Networks and Matroids
"Amortized efficiency of list update and paging rules"
"Average performance of a greedy algorithm for the on-line minimum matching problem on Euclidean space"
"The k-server dual and loose competitiveness for paging,"
--TR

--CTR
Adam Meyerson , Akash Nanavati , Laura Poplawski, Randomized online algorithms for minimum metric bipartite matching, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.954-959, January 22-26, 2006, Miami, Florida
Wun-Tat Chan , Tak-Wah Lam , Hing-Fung Ting , Wai-Ha Wong, A unified analysis of hot video schedulers, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
matching;online algorithms;competitive analysis