Improved Approximation Guarantees for Packing and Covering Integer Programs.
Several important NP-hard combinatorial optimization problems can be posed as  packing/covering integer programs; the  randomized rounding technique of Raghavan and Thompson is a powerful tool with which to approximate them well. We present one elementary unifying property of all these integer linear programs and use the FKG correlation inequality to derive an improved analysis of randomized rounding on them. This yields a  pessimistic estimator, thus presenting deterministic polynomial-time algorithms for them with approximation guarantees that are significantly better than those known.
Introduction
Several important NP-hard combinatorial optimization problems such as basic
problems on graphs and hypergraphs, can be posed as packing/covering integer
programs; the randomized rounding technique of Raghavan & Thompson is a
powerful tool to approximate them well [21]. We present an elementary property
of all these IPs-positive correlation-and use the FKG inequality (Fortuin,
Kasteleyn & Ginibre [10], Sarkar [22]) to derive an improved analysis of randomized
rounding on them. Interestingly, this yields a pessimistic estimator, thus
presenting deterministic polynomial algorithms for them with approximation
guarantees significantly better than those known, in a unified way.
1.1 Previous work
Let Z+ and !+ denote the non-negative integers and the non-negative reals
respectively. For a (column) vector v, let v T denote its transpose, and v i stand
for its ith component. We first define the packing and covering integer programs.
1, a packing (resp. covering) integer program PIP (resp. CIP) seeks to maximize
subject to x
Furthermore if A 2 f0; 1g n\Thetam , we assume that each entry of b is integral. We
Though there are usually no restrictions on the entries of A; b and c aside
of non-negativity, it is easily seen that the above restrictions are without loss
of generality (w.l.o.g.), because of the following. First, we may assume that
ij is at most b i . If this is not true for a PIP, then we may as well set
this is not true for a CIP, we can just reset A ij := b i . Next, by scaling
each row of A such that for each row i and by scaling c so that
we get the above form for A, b and c. Finally, if A 2 f0; 1g n\Thetam ,
then for a PIP, we can always reset b i := bb i c for each i and for a CIP, reset
hence the assumption on the integrality of each b i , in this case.
Remark. The reader is requested to take note of the parameter B; it will
occur frequently in the rest of the paper. Whenever we use the symbol B as a
parameter for any given problem, it will be so since, in the "natural" PIP/CIP
formulation of the problem, B will play the same role as it does in Definition 1.
As mentioned above, PIPs and CIPs model some basic problems in combinatorial
optimization, but most of these problems are NP-hard; hence we
are interested in efficient approximation algorithms for PIPs and CIPs, with
a good performance guarantee. We now turn to an important technique for
approximating integer linear programs-"relaxing" their integrality constraints,
and considering the resulting linear program.
2 The standard LP relaxation of PIPs/CIPs lets x
PIP/CIP, x   and y   denote, resp., an optimal solution to, and the optimum
value of, this relaxation. (For packing, we also allow constraints of the form
set of positive integers fd i g; the LP relaxation sets
Given a PIP or a CIP, we can solve its LP relaxation efficiently. However,
how do we handle the possibility of possibly fractional entries in x   ? We need
some mechanism to "round" fractional entries in x   to integers, suitably. One
possibility is to round every fractional value x
i to the closest integer, with some
tie-breaking rule if x
i is half of an integer. However, it is known that such
"thresholding" methods are of limited applicability.
A key technique to approximate a class of integer programming problems
via a new rounding method-randomized rounding-was proposed in [21]. Given
a positive real v, the idea is to look at its fractional part as a probability-
round v to bvc +1 with probability round v to bvc with probability
bvc. This has the nice property that the expected value of the result is
v. How can we use this for packing and covering problems? Consider a PIP, for
instance. Solve its LP relaxation and set x 0
to be fixed later; this scaling down by ff is done to boost the chance that the
constraints in the PIP are all satisfied-recall that they are all -constraints.
Now define a random z
, the outcome of randomized rounding, as follows.
Independently for each i, set z i to be bx 0
We now need to show that all the constraints in the PIP are satisfied and
that c T \Delta z is not "much below" y   , with reasonable probability; we also need
to choose ff suitably. This is formalized in [21] as follows. As seen above, an
important observation is that E[z i
. Hence,
and
For some fi ? 1 to be fixed later, define events
z is an (fffi)-approximate solution
to PIP if n+1 -
holds. How small a value for (fffi) can we achieve? Bounding
we can pick ff; fi ? 1 such that
using the Chernoff-
Hoeffding (CH) bounds. This gives us an (fffi)-approximation z with nonzero
probability, which is also made deterministic by Raghavan, using pessimistic
estimators [19]. Similar ideas hold for CIPs-the fractions fx
are scaled up by
some ff ? 1 here. Similar approximation bounds are derived through different
methods by Plotkin, Shmoys & Tardos [18]. See Raghavan [20] for a survey of
randomized rounding, and Crescenzi & Kann [7] for a comprehensive collection
of results on NP-optimization problems.
Though randomized rounding is a unifying idea to derive good approximation
algorithms, there are better approximation bounds for specific key problems
such as set cover (Johnson [13], Lov'asz [14], Chv'atal [6]), hypergraph matching
(Aharoni, Erd-os & Linial [1]) and file-sharing in distributed networks (Naor &
Roth [17]), each derived through different means. One reason for this slack
stems from bounding P r(
to quote Raghavan [19],
Throughout, we naively (?) sum the probabilities of all bad events-
although these bad events are surely correlated. Can we prove a
stronger result using algebraic properties (e.g., the rank) of the co-efficient
matrix? A tighter bound for the probabilistic existence
proofs should lead to tighter approximation algorithms.
1.2 Proposed new method
We make progress in the above-suggested direction by exploiting an elementary
property-positive correlation-of CIPs and PIPs. To motivate this idea, let us
just take two constraints of a PIP, and let E 1 and E 2 be the corresponding bad
events, as defined before. For instance, suppose E 1 is the event that 0:1z 1
0:5z stands for the event that 0:4z 1 +0:3z 2 +z 5 +0:1z 6 ?
1:2, where the z i are all independent 0-1 random variables. Now suppose we
are given that E 1 holds. Very roughly speaking, this seems to suggest that
"many" among z 1 ; z 3 ; z 4 and z 6 were "small" (i.e., zero), which seems to boost
the chance that E 2 holds, too. Formally, the claim is that P r(E 2 jE 1
i.e., that P r(E 1
"intuitively clear" fact can then
be easily generalized for us to guess that
Y
In other words, (2) claims that the constraints are positively correlated-given
that all of any given subset of them are satisfied, the conditional probability
that any other constraint is also satisfied, cannot go below its unconditional
probability.
We prove (2), which seems plausible, using the FKG inequality. Thus,
Y
which is always as good as, and most often much better than, (1). (For a
detailed study of the FKG inequality, see, e.g., Graham [11] and Chapter 6 of
Alon, Spencer & Erd-os [2].)
It is not hard to verify such a property for CIPs also. Why we have been so
lucky as to have positive correlation among the constraints of PIPs and CIPs
(a very desirable form of correlation)? The features of PIPs and CIPs which
guarantee this are:
ffl All the entries of the matrix A are non-negative, and
ffl all the constraints "point" in the same direction.
Of course, it can also be shown that given that all of any given subset of the
constraints are violated, the conditional probability that any other constraint
is also violated, cannot go below its unconditional probability; but we will not
have to deal with this situation! Also, such a nice correlation as given by (2)
may not necessarily hold if the z i s are not independent.
More surprisingly, though this new approach usually only guarantees that z
is a "good" approximation with very low (albeit positive) probability-in fact, it
does not even seem to provide a randomized algorithm with any good success
probability-the structure of PIPs and CIPs implies a sub-additivity property
which yields a pessimistic estimator (a notion to be introduced in Section 2);
we thus get deterministic polynomial-time algorithms achieving these improved
approximation bounds. The problem in arriving at a good pessimistic estimator
is that while the previous estimator
(i.e., the one used in [19] and
in related papers) is upper-bounded by E[Z] (for some random variable Z) on
applying the CH bounds, such a fact does not seem to hold here. Nevertheless,
the structure of CIPs/PIPs-in particular, the two simple properties itemized
above-help in providing a good pessimistic estimator. This is a point that we
would like to stress.
Thus we get, in a unified way, improved bounds on the integrality gap
and hence, improved approximation algorithms for all PIPs and CIPs. In par-
ticular, we improve on the above-mentioned results of [13, 14, 1, 17]; our bound
is incomparable with that of [6].
1.3 Approximation bounds achieved
Our best improvements are for PIPs. For PIPs, the standard analysis of randomized
rounding guarantees integral solutions of value
n\Thetam and A 2 f0; 1g n\Thetam . Our
method
improving
well on the previous ones-e.g., in the latter case if y
an integral solution of value \Theta(n), as opposed to the
n) bound.
This method also gives Tur'an's classical theorem on independent sets in graphs
[25] to within a constant factor.
An important packing problem where A 2 f0; 1g n\Thetam is simple B-matching
in hypergraphs [14]: given a hypergraph with non-negative edge weights, finding
a maximumweight collection of edges such that no vertex occurs in more than B
of them. Usual hypergraph matching has 1, and is a well-known NP-hard
problem. To our knowledge, the only known good bound for this problem, apart
from the standard analysis of randomized rounding, was provided by the work
of [1], which focused on the special case of unweighted edges. The methods of [1]
can be used to show that if f is the minimum size of an edge in the hypergraph,
then there exists an integral matching of value at least
(y
(y
While this matches our result to within a constant factor for note that
this bound worsens as B increases, while the standard analysis, as well as our
present analysis, of randomized rounding in fact show that the integrality gap
gets better (decreases) as B increases.
For covering, we prove an
ln(nB=y   )=Bg) (4)
integrality gap, and derive the corresponding deterministic polynomial-time approximation
algorithm. This improves on the
(ln n)=Bg)
bound given by the standard analysis of randomized rounding. Also, Dobson [8]
and Fisher & Wolsey [9] bound the performance of a natural greedy algorithm
for CIPs in terms of the optimal integral solution. Our bound is incomparable
with theirs, but for any given A, c, and the unit vector b=jjbjj 2 pointing in the
direction of b, our bound is always better if B is more than a certain threshold
thresh(A; b; c). See Bertsimas & Vohra [4] for a detailed study of approximating
CIPs; our work improves on all of their randomized rounding bounds except for
their weighted CIPs (wherein it is not the case that c
our bounds are incomparable with theirs.
An important subclass of the CIPs models the unweighted set cover problem:
here. The combinatorial interpretation is
that we have a hypergraph E), and wish to pick a minimum cardinality
collection of the edges so that every vertex is covered. (When viewed as an LP,
this is the "dual" of the hypergraph matching problem.) The rows correspond
to V and the columns, to E. Clearly, this problem requires that x 2 f0; 1g m ,
which is not guaranteed by Definition 1; however, note that for this problem,
any x 2 Z m
trivially yields a y 2 f0; 1g m with Ay - b and
For set cover, we tighten the constants in (4) to derive an
approximation bound. The work of Lund & Yannakakis [15] and Bellare, Gold-
wasser, Lund & Russell [3] shows a constant a ? 0 such that approximating this
problem to within a ln n is likely to take super-polynomial time. However, this
problem is important enough to study approximations parametrized by other
parameters of A; b and c, that are always as good as and often much better than,
\Theta(log n); for instance, the work of [13, 14, 6] shows a ln d+O(1) approximation
bound, where d is the maximum column sum in A-note that d - n. Also since
there is a trivial solution of size n for any set cover instance, n=y   is a simple
upper bound on the approximation ratio. Our bound is a further improvement-
it is easily seen that n=y   - d always, and that there is a constant ' ? 0 such
that for every non-decreasing function f(n) with
exist families of (A; b; c) such that
Thus our bound is never more than a multiplicative (1 + o(1)) or an additive
O(1) factor above the classical bound, and is usually much better; in the best
case, our improvement is by \Theta(log n= log log n). (For instance, we can construct
instances with log log n)
improvement.)
Another noteworthy class of CIPs is related to the B-domination problem:
given a (directed) graph G with n vertices, we want to place a minimumnumber
of facilities on the nodes such that every node has at least B facilities in its out-
neighborhood. This is also a key subproblem in sharing files in a distributed
system [17]; under the assumption that G is undirected and letting \Delta be its
maximum degree, an
approximation bound is presented in [17], improving on the standard analysis
of randomized rounding. Bound (4) improves further on this; in particular,
even if G is directed with maximum in-degree \Delta, (4) shows that the Naor-
Roth bound holds. Furthermore, the comments regarding the \Theta(log n= log log n)
improvement for set cover, hold even in the undirected case. All of this, in turn,
provides better bounds for the file-sharing problem.
Thus, the two main contributions of this work are as follows. The first is
the identification of a very desirable "correlation" property of all packing and
covering integer programs, which enables one to prove, quite easily, improved
bounds on the integrality gap for the linear relaxations of these problems. How-
ever, as shown in Section 4, this is often not constructive, since the probability
of randomized rounding resulting in such good approximations can be (and usually
negligibly small; Section 4 shows a simple family of instances where this
"success probability" is as small as exp(\Gamma\Omega\Gamma n+m)). The second idea, then, is to
show that the structure of PIPs and CIPs in fact presents a suitable pessimistic
estimator (see Section 2 for the definition), which, pleasingly, actually lets us
come up with such approximations efficiently.
In Section 2, we present some basic notions such as large-deviation inequal-
ities, the FKG inequality, and the notion of pessimistic estimators. Section 3
then handles PIPs. We devote Section 4 to the important problem of finding
a maximum independent set problem on graphs by looking at it in the natural
(and well-known) way as a PIP, and make some observations about this prob-
lem; these shine light on the strengths and weaknesses of our approach (and of
related approaches). Section 5 handles CIPs; a good understanding of Section 3
is essential to read this section. Section 6 concludes.
Preliminaries
Let "r.v." abbreviate "random variable" and for any positive integer k, let [k]
denote the set f1; kg. If a universe is understood,
then for any S ' N , -(S) denotes its characteristic vector: -(S) 2 f0; 1g ' with
S. For a sequence s
the vector In our usage, s could be a sequence of reals
or of random variables. As usual, e denotes the base of the natural logarithm.
Remark. Though the following pages seem filled with formulae and calcula-
tions, many of them are routine. The real ideas of this work are contained in
Lemmas 1, 5, and 6. The reader might even consider skipping the proofs of
most of the rest of the lemmas, for the first reading.
We first recall the Chernoff-Hoeffding (CH) bounds, for the tail probabilities
of sums of bounded independent r.v.s [5, 12]. Theorem 1 presents these tail
bounds; see, e.g., Motwani & Raghavan [16] for the proofs.
Theorem 1 Let independent r.v.s, each taking values in
[0; 1], with
and if 0 -
It is easily seen that
Fact 1 (a) G(-;
(d) If
Call a family F of subsets of a set N monotone increasing (resp. monotone
decreasing) if for all S ' T ' N , S 2 F implies that T 2 F (resp., T 2 F implies
that S 2 F). We next present Theorem 2, a special case of the powerful FKG
inequality [10, 22]; for a proof, see, e.g., the proof of Theorem 3.2 in Chapter 6
of [2].
Theorem 2 Given a finite set
suppose we pick a random Y ' N by placing each a i in Y indepen-
dently, with probability p i . For any F ' 2 N , let P r
any sequence of monotone increasing families, and let
any sequence of monotone decreasing families. Then,
s
s
Y
s
s
Y
Finally, we recall the notion of pessimistic estimators [19]. For our purposes,
we focus on the case of independent binary r.v.s. Let
be independent r.v.s with P r(X . Suppose, for
some implicitly defined L ' f0; 1g ' , that
How do we find some v 2 f0; 1g Theorem 3 now presents the idea of
pessimistic estimators applied to the method of conditional probabilities. See
[19] for a detailed discussion and proof.
Notation
and for any j 2 f0; 1g, define wj
Returning to the X i s, p and L, we define
is a pessimistic estimator w.r.t.
(a) U (u(i; w;
is at least
Theorem 3 [19] Let an efficiently computable U be a pessimistic estimator
w.r.t.
by breaking ties arbitrarily, the following algorithm produces a v 62 L:
For
Proof. It is not hard to see by induction on i, that 8i 2 f0g [ ['],
Using this for conjunction with property 2(a) of Definition 3, completes
the proof. 2
Approximating Packing Integer Programs
Let a PIP be given, conforming to Definition 1. We assume that x
is the
constraint on x. (Clearly, even if we have constraints such as x
we will get identical bounds since scaling down by ff ? 1 and then performing
an randomized rounding cannot make x i 62 f0; are
crucial, wherein the structure of PIPs is exploited. It is essential to read this
section before reading Section 5-most proofs are omitted in Section 5 since they
are very similar to the ones in this section.
We solve the LP relaxation, and let the scaling by ff, events
and vectors z; x 0 etc. be as in Section 1.1; ff and fi will be determined later on.
The main point of this section is to present a good candidate for a pessimistic
estimator (see (5)), and to show that it indeed satisfies the conditions of Definition
3. We may then invoke Theorem 3 to show that not only do we get
improved existential results on the integrality gap-that we can also construc-
tivize the existence proof. The work of this section culminates in Theorem 4.
We first setup some notation, to formulate our "failure probability". For
every
denote the ith row
of A. Let independent r.v.s with P r(X
. It is clear that
It is readily verified that
Our first objective is to prove (2) and hence (3), using Theorem 2; this will
then suggest potential choices for a pessimistic estimator. In the notation of
Theorem 2, 1g. For each i 2 [n], define
A little reflection shows the crucial property that each F i is monotone decreas-
ing. Noting that each i, we deduce (2) from Theorem 2. In
fact, a similar proof shows that since the components of X are picked indepen-
dently, we have
Lemma 1 For any j 2 f0g [ [m] and any w 2 f0; 1g j ,
Y
Let
In the notation of Definition 3, the set to be avoided, L, is
We are now ready to define a suitable pessimistic estimator; we first introduce
some useful notation to avoid lengthy formulae.
Notation 2 For all
When j and w are clear from the context, we might just refer to these as h i , f i
and g i .
From Theorem 1 and Lemma 1, a natural guess for a pessimistic estimator,
might be
Y
However, this might complicate matters if h i (j; w) ? 1 and hence we first define
We now define U (u(j; w; p)), 8j 2 f0g [ [m] 8w 2 f0; 1g j , to be
Y
To make progress toward proving that U is a pessimistic estimator w.r.t. X
and L, we next upper-bound P r(E i ) for each i. Recall, by Theorem 1, that for
each
upper-bounds these quantities.
(a) For every i 2 [n],
Proof. (a) Note that Subject to
these constraints and that ff ? 1, we will show that G(- maximized when
prove (a). Now,
If A i \Delta s is held fixed at some fl - 0, (6) is maximized at -
under the constraint that - i 2 [0; \Delta]. Thus,
which is readily shown to be maximized when A i similar proof holds
for (b). 2
Now that we have good tail bounds, we set ff; fi ? 1 such that (fffi) is "small"
and such that for the PIP,
(property (1) of Definition 3). Note that the bound of Lemma 3 makes sense
only handles the common case where A i;j 2 f0; 1g 8i; j, to
get improved bounds which, in particular, work even if We have not
attempted to optimize the constants.
Lemma 3 There exist constants c 1 - 3 and c 2 - 1 for PIP, such that if
Proof. By Lemma 2, it suffices to show that H(y   =ff;
Furthermore, Fact 1(a) shows that
e \Gammay
suffices. Now since B - 1 and there exists a fixed d ? 0
such that
and hence, it suffices if y   =(8ff) ? nde \GammaB(ln ff\Gamma1) . Solving for ff gives the claimed
Lemma 4 There exists a constant c 1 - 3 for PIP instances with A i;j 2 f0; 1g
8i; j, such that if
Proof. Note, since A i;j 2 f0; 1g, that for any i 2 [n],
essentially gets replaced by B+1 in Lemma 3, leading
to the strengthened bounds. 2
As remarked in the introduction, it can be seen that the bounds (on the
approximation ratio (fffi)) of Lemmas 3 and 4 significantly strengthen the corresponding
bounds achievable by the standard analysis of randomized rounding.
At this point, we have exhibited suitable ff and fi such that our function U
satisfies properties (1) and 2(a) of Definition 3. We now turn to proving property
2(b), which is more interesting. Before showing Lemma 6 which proves this, we
first establish a simple lemma which facilitates the proof of Lemma 6.
Lemma 5 For all
Proof. We drop the parameters j and w for the rest of the proof. Part (i)
is easily seen. For part (ii), we first note that
by the definition of these quantities. Now if h
(7) and hence part (ii) above follows from (7), with equality. Instead if h
and furthermore, that
part (ii) follows from (7). Finally if h i - 1, note that h 0
implying (ii) again. 2
Remark. In most previous constructions of pessimistic estimators for various
analyses, equality actually holds in part (ii) of Lemma 5 (as opposed to our
"-"). This then makes it quite easy to prove that the function on hand is a
valid pessimistic estimator. Our task is made more challenging because of this
change in our case.
Lemma 6 For any j 2 f0g [
Thus in particular,
Proof. Let
convenience. Note that
Omitting the parameters j and w in f i , g i etc., it is thus sufficient to show that
Y
Y
Y
Thus from Lemma 5(ii) and since h 0
suffices to show that
Y
Y
Y
which we now prove by induction on n.
Equality holds in (8) for the base case 1. We now prove (8) by assuming
its analogue for show that
(1\Gammag 0
Y
Y
(1\Gammag 0
Simplifying, we need to show that
which holds in view of Lemma 5(i). 2
By now, we have fulfilled all the requirements of Definition 3 and thus present
Theorem 4 There exist constants c 3 ; c 4 ? 0 such that given any PIP conforming
to the notation of Definition 1, we can produce, in deterministic polynomial
time, a feasible solution to it, of value at least
If A 2 f0; 1g m\Thetan , the guarantee on the solution value is at least
Proof. Lemmas 3 and 4 show property (1) of Definition 3. Properties 2(a)
and 2(b) of Definition 3 are shown by Lemmas 1 and 6 respectively. Theorem 3
now completes the proof. 2
4 The Maximum Independent Set Problem on
Graphs
We consider the classical NP-hard problem of finding a maximum independent
set (MIS) in a given undirected graph E), and pose it naturally as a
packing problem. Though we do not get improved approximation algorithms
for this problem, a few observations on this important problem are relevant, as
we shall see shortly.
Tur'an's classical theorem [25] shows that G always has an independent set
of size at least jV such a set can also be found in polynomial
time. The standard packing formulation described below, combined with our ap-
proach, shows the existence of an independent set of
=jEj). The constant
factor hidden in
the\Omega\Gamma \Delta) is weaker than that of Tur'an's theorem however-
our reason for presenting this result is just to show that our approach proves a
few other known results too, in a unified way. We remark that we do not use the
standard notation of graphs having n vertices and m edges, as it will go against
our notation for PIPs and CIPs-the packing formulation has jEj constraints and
Define an indicator variable x for each vertex i, for the presence of
vertex i in the independent set (IS). Subject to the constraint that x i
for every edge (i; j), we want to maximize
. For specific problems like
this, we can get better bounds than does the analysis for Theorem 4, which
uses the general CH bounds. The fractional solution x
for each i, is
optimal to within a factor of 2. Suppose we scale x   down by some ff ? 1
and do the randomized rounding as before. Then for any given edge (i; j),
much better than the CH bound. Analysis
as above then shows that producing
an IS of
One reason for our considering the MIS problem is to show that the failure
probability given by (3) can be extremely close to (though strictly smaller than)
1. This would then underscore the importance of the fact that a pessimistic
estimator can be constructed for PIPs and CIPs. Suppose the graph E)
is a line on the N vertices and that each vertex independently picks
a random bit for itself with the bit being one with probability q, for some
pN be the probability that no two adjacent vertices choose the
bit "1". Setting it is then clear that the
probability that randomized rounding (with the above values for ff and fi) picks
a valid IS in G, equals pN . We now proceed to show that pN is exponentially
small in N , validating our point.
Computing pN by induction on N is standard. Let aN (resp., b N ) denote
the probability that not only do no pair of adjacent vertices both choose "1",
but also that vertex N chooses the bit "1" (resp., 0). Note that
The recurrences
are immediate. Letting -
can then be seen that
Using the facts b we then see that
extremely small. Thus, the success probability of randomized
rounding with our chosen values for ff and fi can be (and usually is) extremely
small, motivating the need for a good pessimistic estimator.
The MIS problem also illustrates the well-known fact that linear relaxations
are not tight in general. As seen above, this problem always has a fractional
solution lying between jV j=2 and jV j. However, the graph G can have its independence
number to be any integer in [jV j] and hence, the integrality gap
of this LP formulation can be quite bad. Furthermore, recent breakthrough
work has shown that the MIS cannot be approximated fast to within any factor
better than jV j ffl for some fixed ffl ? 0, unless some unexpected containment
result holds in complexity theory. This shows that we cannot expect very good
approximation algorithms for all PIPs.
Approximating Covering Integer Programs
Given a CIP conforming to Definition 1, we show how to get a good approximation
algorithm for it. Since most ideas here are very similar to those of
Section 3, we borrow a lot of notation from there, skim over most details and
just present the essential differences.
The idea here is to solve the LP relaxation, and for an ff ? 1 to be fixed later,
to set x 0
j , for each j 2 [m]. We then construct a random integral solution
z by setting, independently for each j 2 [m], z
be as in Section 3. The bad events now are
Analogously to PIPs,
For any i 2 [m], let
Each of these families is monotone increasing now, and thus Theorem 2 again
guarantees Lemma 1, for the present definition of
Suppose we define, given some
analogously as in Notation 2:
As can be expected, the pessimistic estimator U (u(j; w; p)), 8j 2 f0g[ [m] 8w 2
, is now
Y
Now for the analogue of the important Lemma 6. It is easily checked that
Lemma 5(ii) holds again and that instead of part (i) of Lemma 5, we have
Thus, (11) guarantees even now! This shows that Lemma 6 holds for the
current definition of U also.
Thus to establish that U is a pessimistic estimator, we only have to exhibit,
as do Lemmas 3 and 4, ff; fi ? 1 which ensure that U (p first
present a lemma similar to Lemma 2, whose proof is simple and omitted.
Lemma 7 For all
G(y   ff;
We now present the main theorem on covering problems. Since set cover
is an important problem, we present the precise approximation bound for this
problem as a distinct part of the theorem.
Theorem 5 Given a CIP conforming to the notation of Definition 1, we can
produce, in deterministic polynomial time, a feasible solution to it with value at
most
y   (1 +O(maxfln(nB=y   )=B;
ln(nB=y   )=Bg)):
For the unweighted set cover problem, we can improve this to
Proof. For general CIPs, there are two cases: ln(nB=y   )=B is at least one
or at most one. In the former case, we set
For the latter case, we set both ff and fi to be of the form
The proofs follow from standard CH bound analysis using Theorem 1 and Fact 1
with Lemma 7, and the details are omitted.
For the important unweighted set cover problem (see Section 1.3 for the
definition), we observe that for any i 2 [n],
makes the calculations easier. If A i has j non-zeroes (ones) in it, say in columns
then it is not hard to see that P maximized when
Thus,
and hence, by Lemma 7, it suffices to pick ff; fi - 1 such that
G(y   ff;
Now since ff - 1,
Also if we agree to make fi - 2, we then have
G(y   ff;
by Fact 1(b). So from (12), it suffices to choose ff - 1 and 1 - fi - 2 such that
nde \Gammaff - y
It can now be verified that by choosing
for some suitable positive constants a 1 and a 2 , we will satisfy (13). Hence, the
approximation guarantee fffi can be made as small as
worth looking at some concrete improvements brought about by
Theorem 5, over existing algorithms. In the case of unweighted set cover, suppose
d - n is the maximum column sum-the maximum cardinality of any edge
in the given hypergraph. Then, by just summing up all the constraints, we can
see that
y   d - n: (14)
Thus, our approximation bound for the set cover problem-see the second statement
of Theorem 5-is never more by a multiplicative (1 + o(1)) or an additive
O(1) factor above the classical bound of
minfn=y   ;
On the other hand, n=y   - d is quite likely, and it is easy to construct set cover
instances with
log log n) ln(n=y
For instance, we can arrange for just a few edges to have the maximum edge
size of n \Theta(1) , while keeping y   as high as
n= log \Theta(1) n:
Thus in the best case, we get a \Theta(log n= log log n) factor improvement in the
approximation ratio. An important case of the unweighted set cover problem is
the dominating set problem: given a (directed) graph G, the problem is to pick
a minimum number of vertices such that for every one vertex v, at least one
vertex in v [ Out(v) is picked, where Out(v) denotes the out-neighborhood of
v.
We next consider a more general domination-type problem on graphs, modeling
a class of location problems. Given a (directed) graph G with n nodes and
some integral parameter B - 1, we have to place the smallest possible number
of facilities on the nodes of G, so that every node has at least B facilities in its
out-neighborhood-multiple facilities at the same node are allowed.
For the case where G is undirected with maximum degree \Delta, an approximation
bound of
is presented in [17], improving on the
bound given by the standard analysis of randomized rounding. For us, Theorem
5 gives a bound of
ln(nB=y   )=Bg):
Even if G is directed, this new bound is as good or better than
in )=Bg);
where \Delta in denotes the maximum in-degree of G; this is easily seen from the
fact that
which follows from the same reasoning as for (14). We thus get a generalization
of the Naor-Roth result. In the case of undirected graphs, it is not hard to show
families of graphs for which the present bound is better than that of Naor &
Roth's by a factor of upto \Theta(log n= log log n).
In addition to its independent interest, the above problem is a crucial sub-problem
in the following file-sharing problem in distributed networks [17]. Given
an undirected graph G with maximum degree \Delta and a file F of B bits, F must
be stored in some way at the nodes of G, such that every node can recover F
by examining the contents of its neighbor's memories; the aim is to minimize
the total amount of memory used. (Note that solving the above domination
problem is not sufficient for this task.) An approximation bound of
is presented in [17] for this problem. Letting y   be the optimum of the above
domination problem on G, we derive an approximation bound of
which is always as good as (15), and better if B AE ln(\Delta).
6 Concluding Remarks
We have presented a simple but very useful property of all packing and covering
integer programs-positive correlation. This naturally suggests a better
way of analyzing the performance of randomized rounding on PIPs and CIPs.
However, the provable probability of success-of satisfying all the constraints
and delivering a very good approximation-can be extremely low; so, in itself,
this approach may just prove an existential result. Fortunately, the structure
of PIPs and CIPs in fact suggests a pessimistic estimator, thus converting this
existence proof into a (deterministic) polynomial-time algorithm. In our view,
this is very interesting, and gives evidence of the utility of de-randomization
techniques. A common objection to de-randomization is that often, it converts
a fast randomized algorithm that has a good probability of success, to a somewhat
slower deterministic algorithm. However, note that the opposite is true
here! The randomized algorithm suggested by the existence proof can have an
extremely low probability of success; second, solving the LP relaxation heavily
dominates the running time, and the time for running the de-randomization is
comparatively negligible. (This observation about running the LP relaxation,
also suggests that in practice, it would be better to quickly get an approximately
optimal solution to the LP relaxation, since we are anyway dealing with
approximate solutions.)
Another conclusion is that studying correlations helps; this is a well-known
fact in number theory and statistical physics, for instance. In the case of PIPs
and CIPs, we have benefited from the fact that the constraints "help each other",
by being positively correlated. The precise reasons for such a correlation are
spelled out in Section 1.2. It is a challenging open question to use the structure
of correlations in more complicated scenarios; one such problem is the
set discrepancy problem [23, 2]. Given a system of n subsets
a ground set A with n elements, the problem is to come up with a function
such that the discrepancy
is "small", where
While randomized rounding and the method of conditional probabilities can
be used to produce a / with discrepancy O(
log n) [23, 2], a classical non-constructive
result of Spencer shows the existence of a / with
n)
[24]. This is best possible, and it is an important open problem to make this
constructive. If we write down the natural integer programming formulation for
this problem, we can see that each constraint is positively correlated with some
subsets of the constraints, and negatively correlated with others. (There is the
associated observation that in several IPs with both - and - constraints, the -
constraints are often positively correlated amongst each other; similarly for the
- constraints. This idea could potentially bring improvements in some cases.)
It would be very interesting if such more complicated forms of correlation can
be used to get a constructive result here.
Yet another potential room for improvement lies in lower-bounding, in the
context of (2), the ratio
Y
at least for some particular classes of PIPs/CIPs. We know this ratio to be at
least one, by (2); a better lower bound (at least for particular problems) will
lead to better bounds on the integrality gap. Roughly speaking, such better
lower bounds seem plausible especially for PIPs/CIPs wherein "several" columns
have "several" nonzero entries, i.e., in situations where there is heavy (positive)
correlation among the constraints of the IP. This could however be a difficult
problem.
How far can such ideas be pushed? In the general setting of all PIPs and
CIPs, not much progress seems to be possible along these lines, as shown in Section
4. It would however be very interesting to improve our bounds for particular
important problems such as for the edge-disjoint paths problem on graphs. Fur-
thermore, it would be very interesting to study the correlations involved in other
relaxation approaches such as semi-definite programming relaxations.
Finally, as we had seen before, our bounds are incomparable with known
results for some weighted CIPs, e.g., those considered in [6, 4]. It would be
interesting if our method could be extended to include these results also.

Acknowledgements

We thank Moni Naor, Babu Narayanan and David Shmoys for their valuable
comments. Thanks in particular to Prabhakar Raghavan for his insightful suggestions
and pointers to the literature. Thanks are also due to the STOC 1995
program committee and anonymous referee(s) for their helpful comments on the
written style.



--R

Optima of dual integer linear pro- grams
The Probabilistic Method.
Efficient probabilistically checkable proofs and applications to approximation.
Linear programming relaxations
A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.
A greedy heuristic for the set covering problem.
"La Sapienza"

On the greedy heuristic for continuous covering and packing problems.
Correlational inequalities for partially ordered sets.
Application of the FKG Inequality and its Relatives.
Probability inequalities for sums of bounded random vari- ables
Approximation algorithms for combinatorial problems.
On the ratio of optimal integral and fractional covers.
On the hardness of approximating minimization problems.
Randomized Algorithms.
Optimal file sharing in distributed networks.

Probabilistic construction of deterministic algorithms: approximating packing integer programs.
Randomized approximation algorithms in combinatorial op- timization
Randomized rounding: a technique for provably good algorithms and algorithmic proofs.
Some lower bounds of reliability.
Ten Lectures on the Probabilistic Method.
Six standard deviations suffice.
On an extremal problem in graph theory.
--TR

--CTR
Anupam Datta , Sidharth Choudhury , Anupam Basu, Using Randomized Rounding to Satisfy Timing Constraints of Real-Time Preemptive Tasks, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.705, January 07-11, 2002
Benjamin Doerr, Non-independent randomized rounding, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
Aravind Srinivasan, The value of strong inapproximability results for clique, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.144-152, May 21-23, 2000, Portland, Oregon, United States
Aravind Srinivasan, On the approximability of clique and related maximization problems, Journal of Computer and System Sciences, v.67 n.3, p.633-651, November
Yossi Azar , Iftah Gamzu , Shai Gutner, Truthful unsplittable flow for large capacity networks, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
Benjamin Doerr, Non-independent randomized rounding and coloring, Discrete Applied Mathematics, v.154 n.4, p.650-659, 15 March 2006
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
Alon , Dana Moshkovitz , Shmuel Safra, Algorithmic construction of sets for k-restrictions, ACM Transactions on Algorithms (TALG), v.2 n.2, p.153-177, April 2006
Stavros G. Kolliopoulos, Approximating covering integer programs with multiplicity constraints, Discrete Applied Mathematics, v.129 n.2-3, p.461-473, 01 August
Patrick Briest , Piotr Krysta , Berthold Vcking, Approximation techniques for utilitarian mechanism design, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
Aravind Srinivasan, New approaches to covering and packing problems, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.567-576, January 07-09, 2001, Washington, D.C., United States
integer programming;linear programming;positive correlation;combinatorial optimization;correlation inequalities;approximation algorithms;packing integer programs;derandomization;rounding theorems;covering integer programs;linear relaxations;randomized rounding