A Constant-Factor Approximation Algorithm for Packet Routing and Balancing Local vs. Global Criteria.
We present the first constant-factor approximation algorithm for a fundamental problem: the  store-and-forward packet routing problem on arbitrary networks. Furthermore, the queue sizes required at the edges are bounded by an absolute constant. Thus, this algorithm balances a  global criterion (routing time) with a  local criterion (maximum queue size) and shows how to get simultaneous good bounds for both. For this particular problem, approximating the routing time well, even without considering the queue sizes, was open. We then consider a class of such local vs. global problems in the context of covering integer programs and show how to improve the local criterion by a logarithmic factor by losing a constant factor in the global criterion.
Introduction
. Recent research on approximation algorithms has focused a
fair amount on bicriteria (or even multicriteria) minimization problems, attempting
to simultaneously keep the values of two or more parameters "low" (see, e.g., [11, 21,
22, 29, 30, 32]). One motivation for this is that real-world problems often require
such balancing. In this work, we consider a family of bicriteria problems that involve
balancing a local capacity constraint (e.g., the maximum queue size at the links of a
packet routing network, the maximum number of facilities per site in facility location)
with a global criterion (resp., routing time, total cost of constructing the facilities).
Since these global criteria are NP-hard to minimize even with no constraint on the
local criterion, we shall seek good approximation algorithms.
1.1. Packet Routing. Our main result is a constant-factor approximation algorithm
for store-and-forward packet routing, a fundamental routing problem in interconnection
networks (see Leighton's book and survey [14, 15]); furthermore, the
queue sizes will all be bounded by a constant. This packet routing problem has
received considerable attention for more than 15 years, and is as follows:
Definition 1.1 (Store-and-Forward Packet Routing).
We are given an arbitrary N-node routing network (directed or undirected graph)
G, and a set {1, 2, . , K} of packets which are initially resident (respectively) at the
(multi-)set of nodes {s of G. Each packet k is a message that needs
to be routed to some given destination node t k in G. We have to route each packet k
from s k to t k , subject to: (i) each packet k must follow some path in G; (ii) each edge
traversal takes one unit of time; (iii) no two packets can traverse the same edge at
the same unit of time, and (iv) packets are only allowed to queue along the edges of
# Bell Laboratories, Lucent Technologies, 600-700 Mountain Ave., Murray Hill, NJ 07974-0636,
USA. Part of this work was done while at the School of Computing, National University of Singapore,
Singapore 119260, and was supported in part by National University of Singapore Academic Research
Fund Grants RP950662, RP960620, and RP970607. E-mail: srin@research.bell-labs.com.
Dept. of Decision Sciences, National University of Singapore, Singapore 119260, Republic of
Singapore. Supported in part by National University of Singapore Academic Research Fund Grant
RP3970021, and a Fellowship from the Singapore-MIT Alliance Program in High-Performance Computation
for Engineered Systems. E-mail: fbateocp@nus.edu.sg.
G during the routing stage. There are no other constraints on the paths taken by the
packets, i.e., they can be arbitrary paths in G. The NP-hard objective is to select a
path for each packet and to coordinate the routing so that the elapsed time by which all
packets have reached their destinations is minimized; i.e., we wish to keep this routing
time as small as possible.
Extensive research has been conducted on this problem: see [14, 15] and the
references therein. The most desirable type of algorithm here would, in addition
to keeping the routing time and queue sizes low, also be distributed: given a set
of incoming packets and their (source, destination) values, any switch (node of G)
decides what to do with them next, without any other knowledge of the (multi-)set
This would be ideal for parallel computing. (Distributed
algorithms in this context are also termed on-line algorithms in the literature.) Several
such ingenious results are known for specific networks such as the mesh, butterfly, or
hypercube. For instance, given any routing problem with N packets on an N-node
butterfly, there is a randomized on-line routing algorithm that, with high probability,
routes the packets in O(log N) time using O(1)-sized queues [28]. (We let e denote
the base of the natural logarithm, and, for x > 0, lg x, ln x, and respectively
denote log 2 x, log e x, and max{log e x, 1}. Also, Z+ will denote the set of non-negative
Good on-line algorithms here, however, are not always feasible or required, for
the following reasons:
. A large body of research in routing is concerned with fault-tolerance: the
possibility of G being a reasonable routing network when its nodes are subject
to (e.g., random or worst-case) faults. See, e.g., Kaklamanis et al. [12],
Leighton, Maggs & Sitaraman [18], and Cole, Maggs & Sitaraman [6]. In this
case, we do not expect good on-line algorithms, since the fault-free subgraph
G of G has an unpredictable structure. Indeed, a fair amount of research
in this area, e.g., [6, 18], focuses on showing that -
G is still a reasonably
good routing network under certain fault models, assuming global information
about {(s k , t k )} and the fault structure.
. Ingenious on-line algorithms for specific networks such as the butterfly in
the fault-free case [28] are only existentially (near-)optimal. For instance,
the O(lg N) routing time of [28] is existentially optimal to within a constant
factor, since there are families of routing instances that require #(lg N)
time. However, the worst-case approximation ratio can be #(lg N ). It seems
very hard (potentially impossible) to devise on-line algorithms that are near-optimal
on each instance.
. The routing problem can be considered as a variant of unit-demand multi-commodity
flow where all arc capacities are the same, queuing is allowed, and
where delivery time is also a crucial criterion. (Algorithms for this problem
that require just O(1) queue sizes, such as ours, will also scale with network
size.) For such flow problems, the routing problems often have to be run
repeatedly. It is therefore reasonable to study o#-line approximation algo-
rithms, i.e., e#cient algorithms that use the knowledge of the network and of
and have a good approximation ratio.
Furthermore, it seems like a di#cult problem to construct on-line routing algorithms
for arbitrary networks, even with, say, a polylogarithmic approximation guar-
antee. See Ostrovsky and Rabani [26] for good on-line packet scheduling algorithms,
given the path to be traversed for each packet.
By combining some new ideas with certain powerful results of Leighton, Maggs
we present the first polynomial-time o#-
line constant-factor approximation algorithm for the store-and-forward packet routing
problem. Furthermore, the queue sizes of the edges are bounded by O(1). No approximation
algorithms with a sub-logarithmic approximation guarantee were known
for this problem, to the best of our knowledge. For instance, a result from the seminal
work of Leighton & Rao [19] leads to routing algorithms that are existentially
good. Their network embedding of G ensures that there is some routing instance on
G for which their routing time is to within an O(lg N) factor of optimal, but no good
worst-case performance guarantee is known. We may attempt randomized rounding
on some suitable linear programming (LP) relaxation of the problem; however, apart
from di#culties like controlling path lengths, it seems hard to get a constant-factor
approximation using this approach, for families of instances where the LP optimal
value grows as o(lg(N + K)). Our approach uses the rounding theorem of [13] to
select the set of paths that will be used in the routing algorithm of [17]. The analysis
involves an interesting trade-o# between the "dilation" criterion (maximum path
length) and the "congestion" criterion (maximum number of paths using any edge).
1.2. Covering Integer Programs. Let v T denote the transpose of a (column)
vector v. In the second part of the paper, we continue to address the problem of
simultaneously obtaining good bounds on two criteria of a problem. We focus on
the NP-hard family of covering integer programs (CIPs), which includes the well-known
set cover problem. This class of problems exhibits features similar to our
packet routing problem: the latter can be formulated as a covering problem with side
packing constraints. In CIPs, the packing constraints are upper bound constraints on
the variables.
Definition 1.2 (Covering Integer Programs).
Given A # [0, seeks to minimize c T
subject to Ax # b, x # Z n
for each j (the d j # Z+ are given
integers). If A # {0, 1} m-n , then we assume w.l.o.g. that each b i is a positive integer.
we may assume B # 1. A CIP is uncapacitated if
It is well-known that the two assumptions above are without loss of generality.
(i) If A # {0, 1} m-n , then we can clearly replace each b i by #b i #. (ii) Given a CIP
with some A i,j > b i , we can normalize it by first setting A i,j := b i for each such (i, j),
and then scaling A and b uniformly so that #k, (b k # 1 and max # A k,# 1). This is
easily seen to result in an equivalent CIP.
To motivate the model, we consider a concrete CIP example: a facility location
problem that generalizes the set cover problem. Here, given a digraph G, we want
to place facilities on the nodes suitably so that every node has at least B facilities in
its out-neighborhood. Given a cost-per-facility c j of placing facilities at node j, we
desire to place the facilities in a way that will minimize the total cost. It is easy to see
that this NP-hard problem is a CIP, with the matrix A having only zeroes and ones.
This problem illustrates one main reason for the constraints {x j # d j }: for reasons
of capacity, security, or fault-tolerance (not many facilities will be damaged if, for
instance, there is an accident/failure at a node), we may wish to upper bound the
number of facilities that can be placed at individual sites. The more general problem
of "file sharing" in a network has been studied by Naor & Roth [24], where again, the
maximum load (number of facilities) per node is balanced with the global criterion
of total construction cost. For similar reasons, CIPs typically include the constraints
In fact, the case where d
Dobson [7] and Fisher &Wolsey [8] study a natural greedy algorithm GA for CIPs.
For a given CIP, let OPT denote the value of its optimal integral solution. We define
shown in
[8] that GA produces a solution of value at most OPT (1 each row of
the linear system Ax # b is scaled so that the minimum nonzero entry in the row is at
least 1, it is shown in [7] that GA's output is at most OPT (1
Another well-known approach to CIPs is to start with their LP relaxation, wherein
each x j is allowed to be a real in the range [0, d j ]. Throughout, we shall let y # denote
the LP optimum of a given CIP. Clearly, y # is a lower bound on OPT . Bertsimas &
Vohra [5] conduct a detailed study of approximating CIPs and present an approximation
algorithm which finds a feasible solution whose value is O(y # lg m) [5]. Previous
work of this paper's first author [31] presents an algorithm that computes an x # Z n
such that Ax # b and
for some absolute constant a 0 > 0. 1 The bound "x j # d # j may not hold for all j, but
we will have for all j that
for a certain absolute constant a 1 > 0. A related result is presented in [24] for file-sharing

If B is "large" (greater than a certain threshold), then these results significantly
improve previous results in the "global" criterion of keeping c T
compromising
somewhat on the "local" capacity constraints {x j # d j }. This is a common
approach in bicriteria approximation: losing a small amount in each criterion to keep
the maximum such loss "low". In particular, if y # grows at least as fast as me -O(B) ,
then the output value here is O(y # ), while maintaining x
the CIP is uncapacitated, then the above is a significant improvement if B is large.)
We see from (1.2) that in the case where ln
the maximum "violation" are bounded by constants, which is reasonable.
Thus, we consider the case where ln however, the violation
can be as high as 1 which is unsatisfactory. If it
is not feasible (e.g., for capacity/fault-tolerance reasons) to deviate from the local
constraints by this much, then even the gain in the global criterion (caused by the
large value of B) will not help justify such a result. So, a natural question is: is it
possible to lose a small amount in the global criterion, while losing much less in the
local criterion (i.e., in in the case where ln
this in the a#rmative.
(a) For the important special case of unweighted CIPs (#j, c consider the case
parameter #, 0 < # < 1, we present an algorithm
that outputs an x with
1 Recall that To parse the term "ln note that it is
me -B , and is #(1) otherwise.
(ii) the objective function value is at most a 2 y # (1/(1-#)+(1/# 2
for an absolute constant a 2 > 0.
Note the significant improvement over (1.1) and (1.2), particularly if # is a con-
stant: by losing just a constant factor in the output value of the objective function,
we have ensured that each x j /d j is bounded by a constant (at most 1/(1 - #)
This is an improvement over the bound stated in (1.2). In our view, ensuring little loss
in the local criterion here is quite important as it involves all the variables x j (e.g.,
all the nodes of a graph in facility location) and since may be required to
be low due to physical and other constraints.
(b) For the case where the coe#cient matrix A has only zeroes and ones and where
a feasible solution (i.e., #j, x j # d j ) to a (possibly weighted) CIP is really required,
we present an approximation algorithm with output value at most O(y #
This works whether not. While incomparable with the results
of [7, 8], this is better if y # is bigger than a certain threshold. This is also seen to be
an improvement over the O(y # lg m) bound of [5] if y # m a , where a # (0, 1) is an
absolute constant.
Thus, this work presents improved local vs. global balancing for a family of prob-
lems: the basic packet-routing problem (the first constant-factor approximation) and
CIPs (gaining more than a constant factor in the local criterion while losing a constant
factor in the global criterion). The structure of the rest of the paper is as follows. In
-2, we discuss the algorithm for the packet routing problem, which consists mainly
of three steps: (1) constructing and solving an LP relaxation (-2.1); (2) obtaining a
set of routes via suitable rounding (-2.2); and (3) scheduling the packets (-2.3) using
the algorithm of [17]. The nature of our LP relaxation also provides an interesting
re-interpretation of our result, as shown by Theorem 2.4 in -2.3. We discuss in -2.4 an
extension of our idea to a more general setting, where the routing problem is replaced
by a canonical covering problem. In -3, we discuss our results for the general covering
integer programs. We present our improved local vs. global balancing for unweighted
CIPs in -3.1; the case where x j # d j is really required for all j is handled in -3.2, for
the case where the coe#cient matrix has only zeroes and ones. (Note, for instance,
that the coe#cient matrix has only zeroes and ones for the facility location problem
discussed in -1.2.)
2. Approximating the Routing Time to within a Constant Factor. We
refer the reader to the introduction for the definition and motivation for packet rout-
ing. Leighton, Maggs & Rao, in a seminal paper, studied the issue of scheduling the
movement of the packets given the path to be traversed by each packet [16]. They
showed that the packets can be routed in time proportional to the sum of "conges-
tion" and "dilation" of the paths selected for each packet. However, they did not
address the issue of path selection; one motivation for their work is that paths can
plausibly be selected using, e.g., the well-known "random intermediate destinations"
idea [33, 34]. However, no general results on path selection, and hence on the time
needed for packet routing, were known for arbitrary networks G. We address this
issue here by studying the paths selection problem.
Theorem 2.1. There are constants c # , c # > 0 such that the following holds. For
any packet routing problem on any network, there is a set of paths and a corresponding
schedule that can be constructed in polynomial time, such that the routing time is at
most c # times the optimal. Furthermore, the maximum queue size at each edge is
bounded by c # .
We shall denote any path from s k to t k as an (s k , t k )-path. Given a (directed)
path P , E(P ) will denote its set of (directed) edges.
2.1. A Linear Programming Relaxation. Consider any given packet routing
problem. Let us consider any feasible solution for it, where packet k is routed on path
denote the dilation of the paths selected, i.e., D is the length of a longest
path among the P k . Clearly, the time to route all the packets is bounded below by
D. Similarly, let C denote the congestion of the paths selected, i.e., the maximum
number of packets that must traverse any single edge during the entire course of the
routing. Clearly, C is also a lower bound on the time needed to route the packets.
Let N denote the number of nodes in the network and K the number of packets in
the problem. We now present a linear programming (LP) relaxation for the problem;
some of the notation used in this relaxation is explained in the following paragraph.
(ROUTING) min(C +D)/2 subject to:
E(G).
The vector x above is basically a "fractional flow" in G, where x k
f
denotes the
amount of "flow" of packet k on edge f # E(G). The superscript k merely indexes
a packet, and does not mean a kth power. The constraints "N k x model the
requirement that for packet k, (i) a total of one unit of flow leaves s k and reaches
and (ii) at all other nodes, the net inflow of the flow corresponding to packet k,
equals the net outflow of the flow corresponding to packet k. For conciseness, we have
avoided explicitly writing out this (obvious) set of constraints above. Constraints
say that the "fractional congestion" on any edge f is at most C. Constraints
(2.2) say that the "fractional dilation"
f , is at most D. This is a somewhat novel
way of relaxing path lengths to their fractional counterparts.
It is easy to see that any path-selection scheme for the packets, i.e., any integral
flow (where all the x k
f are either 0 or 1) with congestion C and dilation D, satisfies
the above system of inequalities. Thus, since C and D are both lower bounds on the
length of the routing time for such a path-selection strategy, so is (C +D)/2. Hence,
the optimum value of the LP is indeed a lower bound on the routing time for a given
routing problem: it is indeed a relaxation. Note that the LP has polynomial size since
it has "only" O(Km) variables and O(Km) constraints, where m denotes the number
of edges in the network. Thus, it can be solved in polynomial time. Let {x, C , D}
denote an optimal solution to the program. In -2.2, we will conduct a certain type
of "filtering" on x. Section 2.3 will then construct a path for each packet, and then
invoke the algorithm of [17] for packet scheduling.
2.2. Path Filtering. The main ideas now are to decompose x into a set of "flow
paths" via the "flow decomposition" approach, and then to adapt the ideas in Lin-
Vitter [20] to "filter" the flow paths by e#ectively eliminating all flow paths of length
more than 2D.
The reader is referred to Section 3.5 of [1] for the well-known flow decomposition
approach. This approach e#ciently transforms x into a set of flow paths that satisfy
the following conditions. For each packet k, we get a collection Q k of flows along
each Q k has at most m paths. Let P k,i denote the ith path in Q k . P k,i
has an associated flow value z k,i # 0, such that for each k,
words, the unit flow from s k to t k has been decomposed into a convex combination of
)-paths.) The total flow on any edge f will be at most C:
z
the inequality in (2.4) follows from (2.1). Also, let |P | denote the length of (i.e., the
number of edges in) a path P . Importantly, the following bound will hold for each k:
z k,i |P k,i
with the inequality following from (2.2).
The main idea now is to "filter" the flow paths so that only paths of length at
most 2D remain. For each k, define
z k,i .
It is to easy to check via (2.5) that g k # 1/2 for each k. Thus, suppose we define new
flow values {y k,i } as follows for each k: y
if |P k,i | # 2D. We still have the property that we have a convex combination of flow
values: # i y 1. Also, since g k # 1/2 for all k, we have y k,i # 2z k,i for all k, i. So,
implies that the total flow on any edge f is at most 2C:
Most importantly, by setting y all the "long" paths P k,i (those of length
more than 2D), we have ensured that all the flow paths under consideration are of
length at most O(D). We denote the collection of flow paths for packet k by P k . For
ease of exposition, we will also let yP denote the flow value of any general flow path
Remarks. We now point out two other LP relaxations which can be analyzed
similarly, and which yield slightly better constants in the approximation guarantee.
. It is possible to directly bound path-lengths in the LP relaxation so that
filtering need not be applied; one can show that this improves the approximation
guarantee somewhat. On the other hand, such an approach leads
to a somewhat more complicated relaxation, and furthermore, binary search
has to be applied to get the "optimal" path-length. This, in turn, entails
potentially O(lg N) calls to an LP solver, which increases the running time.
Thus, there is a trade-o# involved between the running time and the quality
of approximation.
. In our LP formulation, we could have used a variable W to stand for max{C, D}
in place of C and D; the problem would have been to minimize W subject to
the fractional congestion and dilation being at most W . Since W is a lower
bound on the optimal routing time, this is indeed a relaxation; using our approach
with this formulation leads to a slightly better constant in the quality
of our approximation. Nevertheless, we have used our approach to make the
relationship between C and D explicit.
2.3. Path Selection and Routing. Note that
} is a fractional
feasible solution to the following set of inequalities:
To select one path from P k for each packet k, we need to modify the above fractional
solution to an integral 0-1 solution. To ensure that the congestion does not increase
by much, we shall use the following rounding algorithm of [13]:
Theorem 2.2. ([13]) Let A be a real valued r - s matrix, and y be a real-valued
s-vector. Let b be a real valued vector such that Ay = b and t be a positive real number
such that, in every column of A, (i) the sum of all the positive entries is at most t
and (ii) the sum of all the negative entries is at least -t. Then we can compute an
integral vector y such that for every i, either y
Furthermore, if y contains d non-zero components, the integral
approximation can be obtained in time O(r 3 lg(1
To use Theorem 2.2, we first transform our linear system above to the equivalent
system:
The set of variables above is
}. Note that yP # [0, 1] for
all these variables. Furthermore, in this linear system, the positive column sum is
bounded by the maximum length of the paths in P 1
#P K . Since each path
in any P k is of length at most 2D due to our filtering, each positive column sum is
at most 2D. Each negative column sum is clearly -2D. Thus, the parameter t for
this linear system, in the notation of Theorem 2.2, can be taken to be 2D. Hence by
Theorem 2.2, we can obtain in polynomial time an integral solution y satisfying
For each packet k, by conditions (2.8) and (2.9), we have
1. (Note the
crucial role of the strict inequality in (2.8).) Thus, for each packet k, we have selected
at least one path from s k to t k , with length at most 2D; furthermore, the congestion is
bounded by 2C+2D (from (2.7)). If there are two or more such )-paths, we can
arbitrarily choose one among them, which of course cannot increase the congestion.
The next step is to schedule the packets, given the set of paths selected for each
packet. To this end, we use the following result of [17], which provides an algorithm
for the existential result of [16]:
Theorem 2.3. ([17]) For any set of packets with edge-simple paths having congestion
c and dilation d, a routing schedule having length O(c d) and constant
maximum queue size, can be found in random polynomial time.
Applying this theorem to the paths selected from the previous stage, which have
dilation d # 2D, we can route the packets in time
D). Recall that (C + D)/2 is a lower bound on the length of the optimal
schedule. Thus, we have presented a constant-factor approximation algorithm for the
o#-line packet routing problem; furthermore, the queue-sizes are also bounded by an
absolute constant, in the routing schedule produced. An interesting related point is
that our LP relaxation is reasonable: its integrality gap (worst-case ratio between the
optima of the integral and fractional versions) is bounded above by O(1).
An Alternative View. There is an equivalent interesting interpretation of Theorem 2.1:
Theorem 2.4. Suppose we have an arbitrary routing problem on an arbitrary
graph let L be any non-negative parameter (e.g., O(1), O(lg n), O( # n)).
K} be the set of source-destination pairs for the packets.
Suppose we can construct a probability distribution D k on the (s k , t k )-paths for each
k such that if we sample, for each packet k, an (s k , t k )-path from D k independently of
the other packets, then we have: (a) for any edge e # E(G), the expected congestion on
e is at most L, and (b) for each k, the expected length of the (s k , t k )-path chosen is at
most L. Then, there is a choice of paths for each packet such that the congestion and
dilation are O(L). Thus, the routing can be accomplished in O(L) time using constant-sized
queues; such a routing can also be constructed o#-line in time polynomial in |V |
and K.
We remark that the converse of Theorem 2.4 is trivially true: if an O(L) time
routing can be accomplished, we simply let D k place all the probability on the (s k , t k )-
path used in such a routing.
Proof of Theorem 2.4: Let # k
P denote the probability measure of any (s k , t k )-
path P under the distribution D k . Let supp(D k ) denote the support of D k , i.e., the
set of (s k , t k )-paths on which D k places nonzero probability. The proof follows from
the fact that for any (i,
is a feasible solution to (ROUTING), with C, D replaced by L. Hence by our filter-
round approach, we can construct one path for each packet k such that the congestion
and dilation are O(L). As seen above, the path selection and routing strategies can
be found in polynomial time.
We consider the above interesting because many fault-tolerance algorithms use
very involved ideas to construct a suitable (s k , t k )-path for (most) packets [6]. These
paths will need to simultaneously have small lengths and lead to small edge congestion.
Theorem 2.4 shows that much more relaxed approaches could work: a distribution
that is "good" in expectation on individual elements (edges, paths) is su#cient. Recall
that in many "discrete ham-sandwich theorems" (Beck & Spencer [4], Raghavan &
Thompson [27]), it is easy to ensure good expectation on individual entities (e.g.,
the constraints of an integer program), but is much more di#cult to construct one
solution that is simultaneously good on all these entities. Our result shows one natural
situation where there is just a constant-factor loss in the process.
2.4. Extensions. The result above showing a constant integrality gap for packet
routing, can be extended to a general family of combinatorial packing problems as
follows. Let S k be the family of all the subsets of vertices S such that s k # S and
S. Recall that the (s k , t k )-shortest path problem can be solved as an LP via the
following covering formulation:
c
subject to:
(i,j)#E: i#S,j /
#S
E(G).
Constraint (2.10) expresses the idea that "flow" crossing each s-t cut is at least 1.
The following is an alternative relaxation for the packet routing problem:
(ROUTING-II) min(C +D)/2 subject to:
(i,j)#E: i#S,j /
#S
We can use the method outlined in Section 2.1, 2,2 and 2.3 to show that the
optimal solution of (ROUTING-II) is within a constant factor of the optimal routing
time. A natural question that arises is whether the above conclusion holds for more
general combinatorial packing problems. To address this question, we need to present
an alternative (polyhedral) perspective of our (path) selection routine. First we recall
some standard definitions from polyhedral combinatorics.
Suppose we are given a finite set family F of subsets
of N . For any S # N , let #S # {0, 1} n denote the incidence vector of S. We shall
consider the problem
is a weight function on the elements of N .
Definition 2.5. ([25]) The blocking clutter of F is the family B(F), whose
members are precisely those H # N that satisfy:
P1.
P2. Minimality: If H # is any proper subset of H, then H # violates property P1.
A natural LP relaxation for (OPT
Q is known as the blocking polyhedron of F . The following result is well-known and
easy to check:
F such that #i # F, x i # 1}.
For several classes of clutters (set-systems), it is known that the extreme points
of Q are the integral vectors that correspond to incidence vectors of elements in
F . By Minkowski's Theorem [25], every element in Q can be expressed as a convex
combination of the extreme points and extreme rays in Q. For blocking polyhedra,
the set of rays is
Suppose we have a generic integer programming problem that is similar to (ROUTING-
II), except for the fact that for each k, (2.11) is replaced by the constraint
F k can be any clutter that is well-characterized by its blocking polyhedron Q k (i.e.,
the extreme points of the blocking polyhedron Q k are incidence vectors of the elements
in the clutter F k ). Thus, we have a generalization of (ROUTING-II):
subject to:
Note that the variables x are now indexed by elements of the set N . In the previously
discussed special cases, the elements of N are edges, or pairs of nodes.
The LP relaxation of (BLOCK) replaces the constraint (2.13) by
Theorem 2.6. The optimum integral solution to (BLOCK) has a value that is
at most a constant factor greater than the optimal value to its LP relaxation.
Proof. Let
denote an optimal solution to the LP
relaxation. By Caratheodory's Theorem [25], for each fixed k,
can be
expressed as a convex combination of extreme points and extreme rays of the blocking
polyhedron Q k . However, note that the objective function can only improve by
decreasing the value of
long as the solution remains feasible.
Furthermore, the extreme rays of the blocking polyhedron correspond to vectors v
with each v i non-negative. Thus, without loss of generality, we may assume that the
LP optimum is lexicographically minimal. This ensures that the optimal solution
can be expressed as a convex combination of the extreme points of the polyhedron
alone. As seen above, the extreme points in this case are incidence vectors of elements
of the k-th clutter (we use polyhedral language to let "k-th clutter" denote the
set-system F k ).
Let C and D denote the fractional "congestion" and fractional "dilation" of the
optimal solution obtained by the LP relaxation of (BLOCK). Let A k
2 , . denote
incidence vectors of the elements in the k-th clutter, and let A k
(i) be the ith coordinate
of A k
. Then we have a convex combination, for each k:
Thus, by constraints (2.12), # j:|A k
By filtering out those A k
j with size greater than 2D, we obtain a set of canonical
objects for each k, whose sizes are at most 2D. By scaling the # k
j by a suitable factor,
we also obtain a new set of # k
j such that
.
Using these canonical objects and {# k
} as the input to Theorem 2.2, we obtain a
set of objects (one from each clutter) such that the dilation is not more than 2D and
the congestion not more than 2(C +D). Hence the solution obtained is at most O(1)
times the LP optimum.
Remark. As pointed out by one of the referees, it is not clear whether the lexicographically
minimal optimal solution can be constructed in polynomial time. The
above result is thus only about the quality of the LP relaxation. It would be nice
to find the most general conditions under which the above can be turned into a
polynomial-time approximation algorithm.
3. Improved Local vs. Global Balancing for Covering. Coupled with the
results of [16, 17], our approximation algorithm for the routing time (a global crite-
rion) also simultaneously kept the maximum queue size (a local capacity constraint)
constant; our approach there implicitly uses the special structure of the cut covering
formulation. We now continue the study of such balancing in the context of covering
integer programs (CIPs). The reader is referred to -1.2 for the relevant definitions
and history of CIPs. In -3.1, we will show how to approximate the global criterion
well without losing much in the "local" constraints {x j # d j }. In -3.2, we present
approximation algorithms for a subfamily of the CIPs where x j # d j is required for
all j. One of the key tools used in -3.1 and -3.2 is Theorem 3.3, which builds on an
earlier rounding approach (Theorem 3.2) of [31].
3.1. Balancing Local with Global. The main result of -3.1 is Corollary 3.5.
This result is concerned with unweighted CIPs, and the case where ln
In this setting, Corollary 3.5 shows how the local capacity constraints can be violated
much less in comparison with the results of [31], while keeping the objective function
value within a constant factor of that of [31].
Let exp(x) denote e x ; given any non-negative integer k, let [k] denote the set
{1, 2, . , k}. We start by reviewing the Cherno#-Hoe#ding bounds in Theorem 3.1.
Let G(-, #) .
Theorem 3.1. ([23]) Let X 1 , X 2 , . , X # be independent random variables, each
taking values in [0, 1],
We shall use the following easy fact:
From now on, we will let {x [n]} be the set of values for the variables in
an arbitrary feasible solution to the LP relaxation of the
could be an optimal LP solution.) Let y
Recall that the case
handled well in [31]; thus we shall assume
B. We now summarize the main result of [31] for CIPs as a theorem:
Theorem 3.2. ([31]) For any given CIP, suppose we are given any 1 # <
# such that
holds. Then we can find in deterministic polynomial time, a vector
of non-negative integers such that: (a) (Az) i # b i # for each i # [m], (b)
y #, and (c) z j #x # j #d j # for each j # [n].
The next theorem presents a rounding algorithm by building on Theorem 3.2:
Theorem 3.3. There are positive constants a 3 and a 4 such that the following
holds. Given any parameter #, 0 < # < 1, let # be any value such that #
(a 3 Then we can find in deterministic polynomial time,
a vector non-negative integers such that: (a) (Az) i # b i #(1- #)
for each i # [m], (b) c T
z # a 4 y #, and (c) z j #x # j #d j # for each j # [n].
Remark. It will be shown in the proof of Theorem 3.3 that we can choose, for
instance, a 2. Since there is a trade-o# between a 3 and a 4 that can
be fine-tuned for particular applications, we have avoided using specific values for a 3
and a 4 in the statement of Theorem 3.3.
The following simple proposition will also be useful:
Proposition 3.4. If 0 < x < 1/e, then 1 - x > exp(-1.25x).
Proof of Theorem 3.3: We choose a 2. In the notation of Theorem
3.2, we take #(1 - #) and Our goal is to validate (3.2); by (3.1), it
su#ces to show that
exp(-y
Note that the left- and right-hand sides of (3.3) respectively decrease and increase
with increasing #; thus, since # 0
it is enough
to prove (3.3) for # 0 . We consider two cases.
Case I.
1/e. So, Proposition 3.4 implies that in order to prove (3.3), it su#ces to show that
i.e., that y # 2
# 1.25m exp(-1.5B). This is true from the facts that: (i) m/y #
(which follows from the fact that ln(m/y #
Case II. it su#ces to show that
exp(-y
Recall that 1. So, we have mB/y # > e, i.e., y # /(mB) < 1/e.
Thus,
The inequality follows from Proposition 3.4. So, to establish (3.4), we just need show
that
i.e., that
e, which in turn follows from the facts that
# 1. This completes the proof.
Our required result is:
Corollary 3.5. Given any unweighted CIP with any
parameter #, 0 < # < 1, we can find in deterministic polynomial time, a vector
non-negative integers such that: (a) Av # b, (b)
a is an absolute constant, and
Proof. Let #(a 3 z be as in the statement of Theorem
3.3. for each j. Conditions (a) and (c) are easy to
check, given Theorem 3.3. Since the z j 's are all non-negative integers and since the
CIP is unweighted condition (b) of Theorem 3.3 shows that at most
a 4 y # of them can be nonzero. Thus, condition (b) follows since v j # z j /(#(1-#))+1
if z j > 0 and since v
As mentioned in -1, this improves the value of
[31] to O(1/(1-#)), while keeping (c T
relatively small at O((1/# 2 )-ln
(as long as # is a constant bounded away from 1).
3.2. Handling Stringent Constraints. We now handle the case where the
constraints have to be satisfied and where the coe#cient matrix A has only
zeroes and ones. Recall from -1 that there is a family of facility location problems
where the coe#cient matrix has only zeroes and ones; this is an example of the CIPs
to which the following results apply.
We start with a technical lemma.
Lemma 3.6. For any # > 0, the sum
is at most u
Proof. If
be the highest index such that u r < #/e. Thus, s
ur
it follows that t r # u r ln(#/u r
the last inequality follows from the fact that for any x # y such that x < #/e,
The following simple proposition will also help.
Proposition 3.7. For any # > 0 and # 1,
Proof. The proposition is immediate if # e. Next note that for any a # e, the
function g a decreases as x increases from 1 to infinity. So, if # e and
e, then
Finally, if # > e and # > e, then (ln
Theorem 3.8. Suppose we are given a CIP with the matrix A having only zeroes
and ones. In deterministic polynomial time, we can construct a feasible solution z to
the CIP with z j # d j for each j, and such that the objective function value c T
- z is
O(y
Proof. Let a 3 and a 4 be as in the proof of Theorem 3.3. Define a
and, for any S # [n], y # Starting with S we construct a sequence
of sets S 0 # S 1 # - as follows. Suppose we have constructed S
. If S #, we stop; or else, if all j # S i satisfy a 5
stop. If not, define the proper subset S i+1 of S i to be {j #
to be d j # x note that for all such j,
t be the final set we construct. If S #, we do nothing more; since z j # x # j
for all j, we will have Az # b as required. Also, it is easy to check that z j # d j for all
j. So suppose S t #. Let we stopped at the non-empty set
we see that #x # j # d j for all j # S t . Recall that for all j # S t , we have fixed the
value of z j to be d j # x # j . Let w denote the vector of the remaining variables, i.e.,
the restriction of x # to S t . Let A # be the sub-matrix of A induced by the columns
corresponding to S t . We will now focus on rounding each x # j (j # S t ) to a suitable
non-negative integer z j # d j .
for each i # [m],
A
since z j # x # j for all j # S t , we get
A
Since each b i and A i,j is an integer, so is each b # i . Suppose b # i # 0 for some i. Then,
whatever non-negative integers z j we round the j # S t to, we will satisfy the constraint
So, we can ignore such indices i and assume without loss of generality
that B # .
constraints corresponding to indices i with b # i # 0 can be
retained as "dummy constraints".)
Proposition 3.7 shows that
i.e., that # (a 3 Thus, by Theorem 3.3, we can round
each x # j (j # S t ) to some non-negative integer z j #x # j # d j in such a manner that
the last inequality (i.e., that #(1 - # 1/2) follows from the fact that # a 5 # 2.
So we can check that the final solution is indeed feasible. We only need to bound the
objective function value, which we proceed to do now.
We first bound
Fix any i, 0 # i # t - 1. Recall that for each j # (S i - S i+1 ), we set z
a
Setting substituting (3.7) into (3.6),
where gives the final objective function value. Else
shows that
This, in combination with (3.8) and Lemma 3.6, shows that
This completes the proof.
4. Conclusion. In this paper, we analyze various classes of problems in the
context of balancing global versus local criteria.
Our main result is the first constant-factor approximation algorithm for the o#-
line packet routing problem on arbitrary networks: for certain positive constants c #
and c # , we show that given any packet routing problem, the routing time can e#ciently
be approximated to within a factor of c # , while ensuring that all edge-queues are of size
at most c # . Our result builds on the work of [16, 17], while exploiting an interesting
trade-o# between a (hard) "congestion" criterion and an (easy) "dilation" criterion.
Furthermore, we show that the result can be applied to a more general setting, by
providing a polyhedral perspective of our technique. Our approach of appropriately
using the rounding theorem of [13] has subsequently been applied by Bar-Noy, Guha,
Naor & Schieber to develop approximation algorithms for a family of multi-casting
problems [3]. It has also been applied for a family of routing problems by Andrews &
Zhang [2].
The second major result in the paper improves upon a class of results in multi-criteria
covering integer programs. We show that the local criterion of unweighted
covering integer programs can be improved from an approximately logarithmic factor
to a constant factor, with the global criterion not deteriorating by more than a
constant factor (i.e., we maintain a logarithmic factor approximation).
The third main result improves upon a well-known bound for covering integer pro-
grams, in the case where the coe#cient matrix A has only zeroes and ones. We show
that the approximation ratio can be improved from O(y # lg m) to O(y #
Some open questions are as follows. It would be interesting to study our packet-
routing algorithm empirically, and to fine-tune the algorithm based on experimental
observation. It would also be useful to determine the best (constant) approximation
possible in approximating the routing time. An intriguing open question is whether
there is a distributed packet-routing algorithm with a constant-factor approximation
guarantee. Finally, in the context of covering integer programs, can we approximate
the objective function to within bounds such as ours, with (essentially) no violation
of the local capacity constraints?

Acknowledgements

. We thank Bruce Maggs, the STOC 1997 program committee
and referee(s), and the journal referees for their helpful comments. These
have helped improve the quality of this paper a great deal. In particular, one of the
journal referees simplified our original proof of Lemma 3.6.



--R

Network flows: theory
Packet routing with arbitrary end-to-end delay requirements

Integral approximation sequences.
Rounding algorithms for covering problems.
Routing on butterfly networks with random faults.

On the greedy heuristic for continuous covering and packing problems.
Correlational inequalities for partially ordered sets.
Blocking Polyhedra.
Scheduling to minimize average completion time: O
Asymptotically tight bounds for computing with faulty arrays of processors.
Global wire routing in two-dimensional arrays
Introduction to Parallel Algorithms and Architectures: Arrays
Methods for message routing in parallel machines.
Packet routing and job-shop scheduling in O(congestion+dilation) steps
Fast algorithms for finding O(congestion
On the fault tolerance of some popular bounded-degree networks
An approximate max-flow min-cut theorem for uniform multi-commodity flow problems with applications to approximation algorithms


Scheduling n independent jobs on m uniform machines with both flow time and makespan objectives: a parametric approach.
Randomized Algorithms.
Optimal file sharing in distributed networks.

Universal O(congestion
Randomized rounding: a technique for provably good algorithms and algorithmic proofs.
How to emulate shared memory.


Improved approximation guarantees for packing and covering integer programs.
On the existence of schedules that are near-optimal for both makespan and total weighted completion time
A scheme for fast parallel communication.
Universal schemes for parallel communication.
--TR

--CTR
Stavros G. Kolliopoulos , Neal E. Young, Approximation algorithms for covering/packing integer programs, Journal of Computer and System Sciences, v.71 n.4, p.495-505, November 2005
Stavros G. Kolliopoulos, Approximating covering integer programs with multiplicity constraints, Discrete Applied Mathematics, v.129 n.2-3, p.461-473, 01 August
Konstantin Andreev , Bruce M. Maggs , Adam Meyerson , Ramesh K. Sitaraman, Designing overlay multicast networks for streaming, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
linear programming;approximation algorithms;multicommodity flow;packet routing;rounding theorems;randomized algorithms;covering integer programs;discrete ham-sandwich theorems;randomized rounding