Approximation algorithms for partial covering problems.
We study a generalization of covering problems called partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For example, in <i>k</i>-partial set cover, we wish to choose a minimum number of sets to cover at least <i>k</i> elements. For <i>k</i>-partial set cover, if each element occurs in at most <i>f</i> sets, then we derive a primal-dual <i>f</i>-approximation algorithm (thus implying a 2-approximation for <i>k</i>-partial vertex cover) in polynomial time. Without making any assumption about the number of sets an element is in, for instances where each set has cardinality at most three, we obtain an approximation of 4/3. We also present better-than-2-approximation algorithms for <i>k</i>-partial vertex cover on bounded degree graphs, and for vertex cover on expanders of bounded average degree. We obtain a polynomial-time approximation scheme for <i>k</i>-partial vertex cover on planar graphs, and for covering <i>k</i> points in <i>R<sup>d</sup></i> by disks.
Introduction
Covering problems are widely studied in discrete op-
timization: basically, these problems involve picking
a least-cost collection of sets to cover elements. Classical
problems in this framework include the general
set cover problem, of which a widely studied special
case is the vertex cover problem. (The vertex
cover problem is a special case of set cover in which
the edges correspond to elements and vertices correspond
to sets; in this set cover instance, each element
is in exactly two sets.) Both these problems
are NP-hard and polynomial-time approximation algorithms
for both are well studied. For set cover see
[12, 26, 29]. For vertex cover see [6, 7, 13, 21, 22, 30].
In this paper we study the generalization of "cov-
ering" to "partial covering" [27, 31]. Specifically, in
k-set cover, we wish to find a minimum number (or,
in the weighted version, a minimum weight collec-
tion) of sets that cover at least k elements. When k
is the total number of elements, we obtain the regular
set cover problem; similarly for k-vertex cover.
(We sometimes refer to k-set cover as "partial set
cover", and k-vertex cover as "partial vertex cover";
the case where k equals the total number of elements
is referred to as "full coverage".) This generalization
is motivated by the fact that real data (in clustering
for example) often has errors (also called outliers).
Thus, discarding the (small) number of constraints
posed by such errors/outliers is permissible.
Suppose we need to build facilities to provide service
within a fixed radius to a certain fraction of
the population. We can model this as a partial set
cover problem. The main issue in partial covering
is: which k elements should we choose to cover? If
such a choice can be made judiciously, we can then
invoke a set cover algorithm. Other facility location
problems have recently been studied in this context
We begin our discussion by focusing on vertex
cover and k-vertex cover. A very simple approximation
algorithm for unweighted vertex cover (full cov-
erage) is attributed to Gavril and Yannakakis, and
can be found, e.g., in [14]: take a maximal matching
and pick all the matched vertices as part of the cover.
The size of the matching (number of edges) is a lower
bound on the optimal vertex cover, and this yields a
2-approximation. This simple algorithm fails for the
partial covering problem, since the lower bound relies
on the fact that all the edges have to be covered.
The first approximation algorithm for k-vertex cover
was given in [9]. Their 2-approximation algorithm is
based on a linear programming (LP) formulation:
suitably modifying and rounding the LP's optimal
solution. A faster approximation algorithm achieving
the same factor of 2 was given by Hochbaum [24]
in which the key idea is to relax the constraint limiting
the number of uncovered elements and searching
for the dual penalty value. More recently, Bar-Yehuda
[8] studied the same problem and gave a 2-
approximation for k-vertex cover based on the elegant
"local ratio" method.
1.1. Problem Definitions and Previous
Work
ffl k-Set Cover: Given a set
a collection S of subsets of T ,
cost function c
and an integer k, find a minimum cost sub-collection
of S that covers at least k elements
of T .
Previous Results: For the full coverage ver-
sion, a proposed
by Johnson [26] and Lov'asz [29]. This analysis
of the greedy algorithm can be improved
to H (\Delta) (see the proof in [14]) where \Delta is the
size of the largest set 1 . Chv'atal [12] generalized
this to the case when sets have costs. Slav ' ik
[32] shows the same bound for the partial cover
problem. When
a 4=3-approximation for the full coverage ver-
sion. They extended this result to get a bound
of H (\Delta) \Gamma 1for full coverage. When an element
belongs to at most f sets Hochbaum [21] gives
a f-approximation.
ffl k-Vertex Cover: Given a graph
a cost function and an integer k,
find a minimum cost subset of V that covers at
least k edges of G.
Previous Results: For the partial coverage
version several 2-approximation algorithms are
known (see [9, 24, 8]).
ffl Geometric Covering Problem: Given n
points in a plane, find a minimally sized set of
disks of diameter D that would cover at least k
points.
Previous Results: The full coverage version is
well-studied. This problem is motivated by the
location of emergency facilities as well as from
image processing (see [23] for additional refer-
ences). For the special case of geometric covering
problems, Hochbaum and Maass [25] have
developed a polynomial approximation scheme.
1.2. Methods and Results
ffl k-Set Cover: For the special case when each
element is in at most f sets, we combine a
primal-dual algorithm [13, 18] with a thresholding
method to obtain an f-approximation.
One advantage of our method, in addition to its
simplicity, is that it can be easily parallelized by
changing the algorithm slightly. The resulting
approximation factor is f(1
is any desired constant. The number of parallel
rounds is O(log n) once we fix ffl ? 0. The number
of processors required in linear in the problem
size. This is the first parallel approximation
algorithm for any partial covering problem.
Our general method is as follows: we first
"guess" the cost of the maximum cost set in the
optimal solution. We then modify the original
cost function by raising the costs of some of the
sets to infinity, so that these sets are never chosen
in our solution. This leads to dual feasible
solutions for the instance with modified costs
(which we use as a lower bound) that may be
infeasible for the original problem. However, if
we only raise the costs of sets that are guaranteed
to not be in the optimal solution, we do
not change the optimal IP solution. Hence the
dual feasible solution for this modified instance
is still a lower bound for the optimal IP.
To parallelize the above algorithm, at each
"round" when we update the dual variables we
include all sets whose constraints are "almost"
tight. This is similar to the method described
in [28], but does not work directly. The main
difficulty is that in each round many sets are
chosen. As long as we have covered fewer than
the target number of elements there is no problem
in accounting for the cost of the chosen sets.
However, in the last round (when we cross the
required threshold), we have to carefully pick an
appropriate subset of the chosen sets.
For set cover where the sets have cardinality at
most \Delta there are results (starting from [16, 19])
by Duh and f?rer [15] for set cover (full cover-
age) that improve the H (\Delta) bound to H (\Delta) \Gamma 1For example, for present a 4(=
using "semi-local" optimization
rather than a 11-approximation obtained
by the simple greedy algorithm.
For the case 3, we can obtain a 4bound
for the partial coverage case. This does suggest
that perhaps the H (\Delta) \Gamma 1bound can be
obtained as well. This would improve Slav ' ik's
result [32].
ffl k-Vertex Cover: By switching to a probabilistic
approach to rounding the LP relaxation of
the problem, we obtain improved results for k-vertex
cover, where we wish to choose a minimum
number of vertices to cover at least k
edges. An outstanding open question for vertex
cover (full coverage) is whether the approximation
ratio of 2 is best-possible; see, e.g., [17].
Thus, it has been an issue of much interest to
identify families of graphs for which constant-factor
approximations better than 2 (which we
denote by Property (P)) are possible. In the full
coverage case, Property (P) is true for graphs of
bounded maximum degree; see, e.g., [20]. How
can we extend such a result? Could Property
(P) hold for graphs of constant average degree?
This is probably not the case, since this would
imply that Property (P) holds for all graphs.
(Given a graph G with n vertices, suppose we
add a star with \Theta(n 2 ) vertices to G by connecting
the center of the star by an edge to
some vertex of G. The new graph has bounded
average degree, and its vertex-cover number is
one more than that of G.) However, we show
that for expander graphs of bounded average
degree, Property (P) is indeed true. We also
show Property (P) for k-vertex cover in the case
of bounded maximum degree and arbitrary k;
this is the first Property (P) result for k-vertex
cover, to our knowledge. Our result on expanders
uses an expectation analysis and the expansion
property. Expectation analysis is insufficient
for our result here on k-vertex cover, and
we show that a random process behaves close to
its mean on bounded-degree graphs: the degree-
boundedness helps us show that many sub-events
related to the process are (pairwise) in-
dependent. We also present certain new results
for multi-criteria versions of k-vertex cover.
ffl Geometric Covering: There is a polynomial
approximation scheme based on dynamic programming
for the full coverage version [25]. For
the partial coverage version since we do not
know which k points to cover, we have to define
a new dynamic program. This makes the implementation
of the approximation scheme due
to Hochbaum and Maass [25] more complex, although
it is still a polynomial-time algorithm.
ffl k-Vertex Cover for Planar Graphs: We
are able to use the dynamic programming
ideas developed for the geometric covering problem
to design a polynomial-time approximation
scheme (PTAS) for k-vertex cover for planar
graphs. This is based on Baker's method for
the full covering case [3].
2. k-Set Cover
The k-Set Cover problem can be formulated as an
integer program as follows. We assign a binary variable
1g. In this for-
mulation, belongs to the cover. A
binary variable y i is assigned to each element t
covered. Clearly, there could be
at most n \Gamma k such uncovered elements.
The corresponding LP relaxation can be obtained
by letting the domain of x j and y i be
1. Notice that the upper bound on x j and y i is
unnecessary and is thus dropped.
min
subject to
The dual LP contains a variable u i (for each element
corresponding to each of the first
n constraints in the above LP. The dual variable
z corresponds to the (n th constraint in the
above LP formulation. The dual LP is to maximize
subject to: (i)
and (iii) z - 0.
The algorithm SetCover (pseudo-code can be
found in Figure 1 in Appendix A) does the follow-
ing. The algorithm "guesses" the set with the highest
cost in the optimal solution by considering each
set in turn to be the highest cost set. For each set
that is chosen, to be the highest cost set, say S
along with all the elements it contains is removed
from the instance and is included as part of the cover
for this guess of the highest cost set. The cost of all
sets having a higher cost than c(S j ) is raised to 1.
I is the modified instance. Set-
Cover then calls Primal-Dual on I j which uses a
primal dual approach [18] to return a set cover for I j .
In Primal-Dual, the dual variables u i are increased
for all t there exists a set S i such that
are chosen this way until
the cover is feasible. The algorithm then chooses
the minimum cost solution among the m solutions
found. For the purpose of clarity of exposition in
the following pseudo-code (refer to Figure 1 in Appendix
we assume that costs of all sets in S are
distinct.
Theorem 2.1: returns a f -
approximate solution, where f is the highest frequency
of any element i.e. an element appears in
at most f sets.
Proof: Let OPT refer to an optimal solution. We
will use OPT to mean either an optimal solution
or the cost of an optimal solution. The meaning
will be clear from the context in which it is used.
Let I be the given instance of the problem. Let
I j refer to the modified instance of the problem i.e.
I h be the set with the
highest cost in OPT . Let OPT (I h ) be the optimal
integer solution for the instance I h .
refer to the dual
feasible solution for the instance I h . Again, DFS(\Delta)
will be used to mean the dual feasible solution or the
cost of the dual feasible solution. DFS(I h ) may not
be a feasible solution 2 to the instance (T j
(note the original cost function). However, since
we have DFS(I h is the
set cover chosen by our algorithm during the iteration
l be the last set chosen. Let
stands for Almost Set
Cover). Note that since S h is the costliest set,
represent the set of points
covered by ASC. Let T represent the set
of uncovered elements. Since the algorithm chooses
a cover, SC, of the lowest cost, cost(SC) is upper
bounded by cost(SC h ).
2 This is because we relax the constraints for the dual
problem.
approximate solution for k-Vertex Cover.
2.1. Parallel Implementation of Partial Set
Cover Algorithm
We assume as before that each element belongs
to at most f sets. The framework for the algorithm
is the same as the one we described for the
primal-dual serial algorithm. The parallel algorithm
runs in "rounds". In each round, we simultaneously
raise all dual variables u i corresponding to
the uncovered elements. In the serial algorithm
we pick one set in each iteration, namely a set S j
such that (
(Recall that c 0
denotes the modified cost function.) We change
this step in the algorithm to pick all sets such that
let us prove that c 0 (S
stop as soon as we have covered at least k elements.
Suppose the algorithm covers at least k elements
after ' rounds. The main problem is that in the
last round we can include many sets simultaneously,
while we can afford to include only a few. Let ffi be
the number of elements that we need to cover after
round To select an appropriate subset of the
chosen sets, we need to pick a minimal collection of
chosen sets that cover at least ffi elements. To accomplish
this, we order the sets chosen in the last
iteration arbitrarily. Now compute in parallel the
"effective" number of elements each set covers and
choose a minimal collection based on the fixed order-
ing. (All these steps can be implemented in parallel
using prefix computations.)
Theorem 2.3: The parallel algorithm runs in (1
f log(1=ffl))(1+log n) rounds. The number of processors
is linear in the size of the input. The parallel
algorithm produces a f
-approximate solution.
3. Set Cover for Small Sets
Problem: Given a collection C of small subsets of
a base set U . Each small subset in the collection has
size at most \Delta, and their union is U . The objective
is to find a minimum size sub-collection that covers
at least k elements.
Here we have the original partial set cover instance
with the additional information that the sets are of
"small" size, i.e., \Delta is small. We obtain an approximation
factor of 4=3 for the case when using
the the idea of (s; t) semi-local optimization [15].
This technique consists of inserting up to s 3-sets
(sets of size 3) and deleting up to t 3-sets from the
current cover. Then the elements that are not covered
by the 3-sets (already existing ones + the newly
added) are covered optimally using 2-sets and 1-sets.
This can be solved in polynomial time using maximum
matching [16]. The vertices are the uncovered
elements of U and the edges are the admissible
2-sets. The 2-sets corresponding to the maximum
matching edges and the 1-sets corresponding to the
vertices not covered by the maximum matching form
an optimum covering. We will order the quality of
a solution by the number of sets in the cover and
among two covers of the same size we choose the one
with fewer 1-sets and if the covers have the same size
and neither cover has a 1-set we choose the one that
covers more elements.
The algorithm starts with any solution. One solution
can be obtained as follows. Choose a maximal
collection of disjoint 3-sets. Cover the remaining elements
optimally using 2-sets and 1-sets. Perform
semi-local (2; 1) improvements until no improvement
is possible.
The proof for the bound of 4=3 for full coverage
does not extend to the partial coverage version. For
the full coverage, to prove the lower bound on the
optimal solution Duh and f?rer construct a graph G
in which the vertices are the sets chosen by OPT and
the edges are 1-sets and 2-sets of the approximate
solution. They prove that G can not have more than
one cycle and hence argue that the total number of
1-sets and 2-sets in the solution is a lower bound on
OPT . This works well for the full coverage version
but breaks down for the partial covering problem.
For the partial covering case G having at most one
cycle is a necessary but not a sufficient condition to
prove the lower bound.
In the full version of the problem, to bound the
number of 1-sets in the solution they construct a
bipartite graph with the two sets of vertices corresponding
to the sets chosen by the approximate
solution and OPT . If a set corresponding the approximate
solution intersects a set corresponding to
OPT in m elements then there are m edges between
their corresponding vertices in the graph. In each
component of the graph they show that the number
of 1-sets of the solution in that component is
at most the number of 1-sets of OPT in that com-
ponent. This is clearly not the case in the partial
covering case. We obtain a bound on the number
of 1-sets as a side effect of the proof for the lower
bound on OPT .
The detailed proof of our theorem is shown in Appendix
B.
Theorem 3.1: The semi-local (2; 1)-optimization
algorithm for 3-set partial covering problem produces
a solution that is within 4OPT + 1.
4. Probabilistic Approaches for k-Vertex
Cover
We now present a randomized rounding approach
to the natural LP relaxation of k-vertex cover. Analyzed
in three different ways, this leads to three
new approximation results mentioned in x1: relating
to vertex cover (full coverage) for expander
graphs of constant average degree, k-vertex cover on
bounded-degree graphs, and multi-criteria k-vertex
cover problems. We first describe the basic method
and prove some probabilistic properties thereof, and
then consider the three applications.
The k-vertex cover problem on a graph E)
can be formulated as an integer program as follows.
We assign binary variables x j for each v
z i;j for each (i; In this formulation, x
vertex belongs to the cover, and z
(i; covered. The corresponding LP relaxation
can be obtained by letting each x j and z i;j lie in
min
subject to
z
Our basic approximation recipe will be as follows.
The LP relaxation is solved optimally. Let fx
fz
i;j g denote an optimal LP solution, and let
is a parameter that will be
chosen based on the application. Let S
1=-g, and S Include all the vertices in
as part of our cover, and mark the edges incident
on vertices in S 1 as covered. Now independently for
each j 2 S 2 , round x j to 1 with a probability of
-x
, and to 0 with a probability of
. Let
W be the random variable denoting the number of
covered edges at this point. If W ! k, we choose any
uncovered edges and cover them by arbitrarily
choosing one end-point for each of them.
We now introduce some notation to analyze the
above process. Throughout, we let Pr[\Delta] and E[\Delta] denote
probability and expectation, respectively. Let
y   represent the optimal objective function value of
the LP, and define S
1g.
Let y
F and y
P be the contribution to y   of the vertices
in S 0 and respectively. Denote by U i;j
the event that edge (i; j) is uncovered. Let C 1 be
the cost of the solution produced by our randomized
scheme before the step of covering k \Gamma W edges if
necessary, and let C 2 be the cost incurred in covering
these any. The total cost C is of
course
it is easy to check that E[C 1
P , and that
The following lemma on the statistics of W will
be useful. As usual, let E denote the complement of
an event E .
Lemma 4.1: (i) E[W Suppose the
graph G has maximum degree d. Then, the variance
of W is at most dE[W ].
Proof: (i) Consider any edge (i; j). Now if x
1=- or x
Consider the latter case. Since
x
i;j , we can check that for any given z
maximized when x
x
i;j =2. Hence,
Thus, since E[W
(i;j)2E Pr[U i;j ], we get
z
(ii) We have
(i;j)2E U i;j . It is also an easy
calculation to see that if a random variable W 0 is
the sum of pairwise independent random variables
each of which lies in [0; 1], then
However, the terms U i;j that constitute W do have
some dependent pairs: if edges (i; j) and (i
an endpoint, then U i;j and U i 0 ;j 0 are dependent (pos-
itively correlated). Define fl to be the sum, over
all unordered pairs of distinct edges (i; j) and (i
that share an end-point, of Pr[U i;j - U i 0 ;j 0 ]. Using
the above observations and the definition of variance,
a moment's reflection shows that Var[W ] is upper-bounded
by E[W events A and
B,
Thus, the term "Pr[U i;j - U i 0 ;j 0 ]" in fl is at most
Finally, since each edge has
at most 2(d \Gamma 1) other edges that share an end-point
with it, we get that
4.1. Vertex Cover on Expanders
Suppose we have a vertex cover problem; i.e., k-vertex
cover with m. The LP relaxation here
has "1" in place of "z i;j " in (1), and does not require
the variables z i;j and the constraint (2). We focus
here on the case of expander graphs of constant average
degree. That is, for some constants c and d, we
are studying graphs where: (i) the number of edges
m is at most nd, and (ii) for any set X of vertices
with jX j - n=2, at least cjX j vertices outside X have
a neighbor in X .
m, it is well-known that we can efficiently
compute an optimal solution x   to the
LP with all entries lying in f0; 1=2; 1g. Let
1g. Also, since
shows
that E[C] is at most y
overall approach of: (i) conducting a randomized
rounding and then doing a greedy fixing of violated
constraints, and (ii) using an equality such as our
here, is suggested
in [33]. We next show how the expansion property
is useful in bounding E[C] well. However, in
the context of partial covering, an equality such as
does not hold; so, as
discussed in x4.2 and x4.3, new analysis approaches
are employed there.) Choosing
H =m to minimize
y
Case I: jH j - n=2. Note that the edges incident
on vertices in H must have their other end-point in
otherwise the LP constraint on such edges will be
violated. Since G is an expander, jF j - c \Delta jH j. Also,
y
F ,
we have y
a) for some a - 2c. We can
now use (4) to get
i.e., at most since a - 2c.
Case II:
(4) shows that E[C] -
nd by assumption. So, E[C] -  in this
case.
Thus we see that E[C] - [2
In other words, for the family of
expanders of constant average degree, we can get a
constant-factor approximation that is strictly better
than 2.
4.2. k-Vertex Cover: Bounded-Degree
Graphs
We now show that any constant d, k-vertex cover
on graphs of maximum degree at most d can be approximated
to within 2(1
any value of
the parameter k. We also demonstrate that the integrality
gap in this case is at most 2(1
\Gamma\Omega\Gamma2 =d)). We
start with a couple of tail bounds that will be of use
now, as well as in x4.3. First, suppose X is a sum
of independent random variables X i each of which
lies in [0; 1]; let E[X
the Chernoff bound shows that Pr[X -(1
is at most e \Gamma-ffi 2 =3 . We will also need tail bounds
for certain non-independent situations. Suppose X
is a random variable with mean - and variance oe
suppose a ? 0. Then, the well-known Chebyshev's
inequality states that Pr[jX \Gamma -j - a] is at most
We will need stronger tail bounds than this,
but only on X's one-sided deviations (say, below its
mean). We will use the Chebyshev-Cantelli inequality
(see, e.g., [1]), which shows that Pr[X \Gamma -
We now analyze the performance of our basic algorithm
(of randomized rounding of the LP solution
followed by a simple covering of a sufficient
number of edges), for the k-vertex cover problem
on graphs with maximum degree bounded by some
given constant d. The notation remains the same.
The main problem in adopting the method of x4.1
here is as follows. Since k equaled m there, we could
use the equality E[maxfk \Gamma W;
thus substantially simplifying the analysis. Here,
however, such an equality is not true; furthermore,
any pair of
random variables X; Y . (In fact, the two sides of this
inequality may differ a lot. For instance, suppose
X is the sum of n independent random variables,
each of which is uniformly distributed on f\Gamma1; 1g;
let Y be the constant 0. Then the r.h.s. is zero,
while the l.h.s. is \Theta(
n).) Instead, we take recourse
to the Chebyshev-Cantelli inequality, and use
Lemma 4.1(ii).
We now claim that
This is trivially true if k ! 4d, since Pr[W -
suppose k - 4d. Lemma 4.1 and the Chebyshev-
Cantelli inequality show that - :
and that Pr[W
d- 1=5. Subject to
d- is minimized
Thus we have (5).
Next, for a suitably large constant c 0 , we can assume
that k - c 0 d 5 . (Any optimal solution has size
at most k, since in an optimal solution, every vertex
should cover at least one new edge. So if k is
bounded by a constant-such as c 0 d 5 -then we can
find an optimal solution in polynomial time by exhaustive
search.) Also, by adding all the constraints
of the LP and simplifying, we get that y   - k=d.
Thus, letting a Chernoff bound shows
that immediately after the randomized rounding, the
probability of having more than 2y
vertices in our initial cover is at most 1=5 (if the
constant c 0 is chosen large enough). Recall (5). So,
with probability at least 1 3=5, the
final cover we produce is of size at most
2y
kd:
We now choose
sufficiently large, some simplification
shows that the final cover size is at most 2y
4.3. k-Vertex Cover: Multiple Criteria
We now briefly consider multi-criteria k-vertex cover
problems on arbitrary graphs. Here, we are given
a graph G and, as usual, have to cover at least k
edges. We are also given ' "weight functions" w i ,
and want a cover that is "good" w.r.t. all of these.
More precisely, suppose we are given vectors
and a fractional solution x   to the k-cover problem
on G. Define y
'. We aim for an integral solution z such that
for each i, y
is not "much above"
y
. Multi-criteria optimization has recently received
much attention, since participating individu-
als/organizations may have differing objective func-
tions, and we may wish to (reasonably) simultaneously
satisfy all of them if possible. The result
we show here is that if y
n) for all
(where c is a sufficiently large constant), then
we can efficiently find an integral solution z with
for each i. Please see


Appendix

C for a short description of the analysis.
5. Geometric Packing and Covering
Problem: Given n points in a plane, find the smallest
number of (identical) disks of diameter D that
would cover at least k points.
A polynomial time approximation scheme exists
for the case when (full covering). The algorithm
uses a strategy, called the shifting strategy.
The strategy is based on a divide and conquer ap-
proach. The area, I , enclosing the set of given points
is divided into strips of width D. Let l be the shifting
parameter. Groups of l consecutive strips, resulting
in strips of width lD are considered. For any fixed
subdivision of I into strips of width D, there are l
different ways of partitioning I into strips of width
lD. The l partitions are denoted by S 1
The solution to cover all the points is obtained
by finding the solution to cover the points for each
l, and then choosing a minimum
cost solution. A solution for each partition is
obtained by finding a solution to cover the points in
each strip (of width lD) of that partition and then
taking the union of all such solutions. To obtain a
solution for each strip, the shifting strategy is re-applied
to each strip. This results in the partition of
each strip into "squares" of side length lD. As will
be shown later, there exists an optimal covering for
such squares.
We modify the use of shifting strategy for the case
when k - n (partial covering). The obstacle in directly
using the shifting strategy for the partial covering
case is that we do not know the number of
points that an optimal solution covers in each strip
of a partition. This is not a problem with the full
covering case because we know that any optimal solution
would have to cover all the points within each
strip of a partition. For the partial covering, this
problem is overcome by "guessing" the number of
points covered by an optimal solution in each strip.
This is done by finding a solution for every possible
value for the number of points that can be covered
in each strip and storing each solution. A formal
presentation is given below.
Let A be any algorithm that delivers a solution to
cover the points in any strip of width lD. Let A(S i )
be the algorithm that applies A to each strip of the
partition S i and outputs the union of all disks in a
feasible solution. We will find such a solution for
each of the l partitions and output the minimum.
Consider a partition S i containing p strips of width
lD. Let n j be the number of points in strip j. Let
j be the number of points covered by OPT in
strip j. Since we do not know n OPT
, we will find feasible
solutions to cover points for all possible values
of n OPT
. Note that 0 - n OPT
We use dynamic programming to solve our problem.
The recursive formulation is as follows:
x
(D x
where C(x; y) denotes the number of disks needed to
cover y points in strips 1::x and D x
i is the number of
disks needed to cover i points in strip x. Computing
us the desired answer.
For each strip s, for
i can be calculated
by recursive application of the algorithm to the
strip s. We partition the strip into squares of side
length lD. We can find optimal coverings of points
in such a square by exhaustive search. With O(l 2 )
disks of diameter D we can cover lD \ThetalD square com-
pactly, thus we never need to consider more disks for
one square. Further, we can assume that any disk
that covers at least two of the given points has two of
these points on its border. Since there are only two
ways to draw a circle of given diameter through two
given points, we only have to consider 2
pos-
sible disk positions where n 0 is the number of given
points in the considered square. Thus, we have to
check for at most O(n 02(l
arrangements of disks.
Let Z A be the value of the solution delivered by
algorithm A. The shift algorithm SA is defined for
a local algorithm A. Let r B denote the performance
ratio of an algorithm B; that is, r B is defined as the
supremum of Z problem instances.
l ) where A is the local
algorithm and l is the shifting parameter.
Proof: Consider a partition S i with p strips of width
lD. We have that r A - Z A
runs over all
strips in partition S i and jOPT j j is the number of
disks in an optimal cover of n OPT
points in strip j.
It follows that Z A(S i
Let OPT be the set of disks in an optimal solution
and OPT (l) the set of disks in OPT covering
points in two adjacent lD strips in
shifts respectively. Thus we have
l
l
l
r A (
l
l
r A (
l
There can be no disk in the set OPT that covers
points in two adjacent strips in more than one shift
partition. Therefore, the sets OPT
are disjoint and can add up to at most OPT . It follows
that
Substituting this in the bound above for Z SA we get
that Z SA is at most 1
l r A :(l
Theorem 5.2: The above algorithm yields a PTAS
with performance ratio at most (1
l
Proof: We use two nested applications of the shifting
strategy to solve the problem. The above lemma
applied to the first application of the shifting strategy
would relate the performance ratio of the final
solution, r SA , to that of the solution for each strip,
r A .
The lemma when applied to the second application
of shifting strategy relates r A to the performance
ratio of the solution to each square, say r A 0 . Thus,
1=l). But since we obtain an optimal
solution for each square, r A
that r SA - (1
6. k-Vertex Cover for Planar
Graphs
Full vertex cover for planar graphs of bounded tree-width
can be computed optimally in linear time.This
immediately leads to a PTAS for planar graphs
by a combination of results of Baker and Bodlaender
[3, 4]. Baker gives a general framework that constructs
a PTAS for any problem which can be solved
optimally for l-outerplanar graphs - planar graphs
where all nodes have a path of length - l to a node
on the outermost face [3]. This method is based on
the shifting strategy that is similar to the method
used for geometric covering in the previous section.
Bodlaender [4] proves that any l-outerplanar graph
has tree-width at most 3l \Gamma1. Vertex cover for graphs
of bounded tree-width can be solved optimally in
polynomial time, thus implying such a solution for
graphs that are l-outerplanar for a fixed constant l.
First we describe how to create a collection of decompositions
of a planar graph G into a set of l-
outerplanar graphs. Let shortest path length
from v to any node on the outer face of G. For
each value of we generate a decomposition
as follows. Let G be the i th
l-outerplanar graph for a fixed ffi . V
g. There are l different ways of creating these de-
compositions, one for each ffi. These correspond to
the l partitions l in the geometric covering
case. In the full covering case, the algorithm is to
find a vertex cover for each of the l decompositions
and then to take the best solution. The vertex cover
for each decomposition is the union of the solutions
to each l-outerplanar graph in the decomposition.
As in the case of geometric covering the obstacle in
directly using the above algorithm for the partial
covering case is that we do not know the number
of edges covered by OPT in each outerplanar graph.
As in the previous section, we overcome this obstacle
by "guessing" the number of points covered by an
optimal solution in each l-outerplanar graph. The
dynamic programming formulation in the previous
section can be used once the following correspondence
between the various entities is noted. The
vertices in our case correspond to the disks and the
edges correspond to the points to be covered. An l-
outerplanar graph corresponds to the strip of width
lD. As in the previous case, we still have l such
decompositions. In the geometric covering problem
the solution to each strip is calculated by recursively
applying the shifting strategy to each strip. In this
case, an optimal solution for the partial vertex cover
for l-outerplanar graphs is computed as shown in the
next section.
We now give a linear-time algorithm for bounded
tree-width graphs (if the graph has tree-width l, then
the time required for the algorithm to run will be
exponential in l but linear in the size of the graph).
The following definition is standard (see, e.g., [4]).
E) be a graph. A tree-decomposition
of G is a pair (fX
is a family of subsets
of V and tree with the following
properties:
1.
2. For every edge there is a subset
3. For all lies on the path from i to
k in T , then X i
The tree-width of a tree-decomposition (fX
1g. The tree-width of a graph
is the smallest value k such that the graph has a tree-decomposition
with tree-width k.
Many problems are known to have linear time algorithms
on graphs with constant tree-width, and
there are frameworks for automatically generating
a linear time algorithm, given a problem specification
in a particular format [2, 5]. The partial vertex
cover problem can be solved by successively using
solutions to the problem of finding the maximum
number of edges that can be covered using
vertices. The value of p can be selected by doing
a binary search on the set of vertices which reduces
in half with every successive solution. This
problem can be expressed in the formalism of [5]
as:
which states that we want to maximize the set of
edges that can be covered by any subset V 1 of V
such that the size of V 1 is at most p.
Theorem 6.1 follows from Lemma 5.1 and the fact
that r A = 1.
Theorem 6.1: The above algorithm gives a PTAS
with a performance ratio -
l ).



--R

An asymptotic isoperimetric inequality.
Easy Problems for Tree-Decomposable Graphs
Approximation Algorithms for NP-Complete Problems on Planar Graphs
Some classes of graphs with bounded tree width.
Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
A linear time approximation algorithm for the weighted vertex cover problem.
A local-ratio theorem for approximating the weighted vertex cover problem
Using homogeneous weights for approximating the partial cover problem.
Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem
Approximation algorithms for covering problems.
Algorithms for Facility Location Problems with Outliers.
A greedy heuristic for the set-covering problem
A modification of the greedy algorithm for the vertex cover.
"Introduction to Algorithms"

A modified greedy heuristic for the set covering problem with improved worst case bound.
The Lov'asz theta function and a semidefinite programming relaxation of vertex cover.
A general approximation technique for constrained forest problems.
Approximating k-set cover and complementary graph coloring
Improved approximation algorithms for the vertex cover problem in graphs and hyper- graphs
Approximation algorithms for the set covering and vertex cover problems.
Efficient bounds for the stable set
Approximation Algorithms for NP-hard problems

Approximation schemes for covering and packing problems in image processing and VLSI.
Approximation algorithms for combinatorial problems.
The computational complexity of machine learning.
A Primal Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Cover.
On the ratio of optimal integral and fractional covers.
Structural properties and algorithms.
The hardness of approximation: Gap location.

New Approaches to Covering and Packing Problems.
--TR
Introduction to algorithms
Easy problems for tree-decomposable graphs
Approximation algorithms for NP-complete problems on planar graphs
A modified greedy heuristic for the set covering problem with improved worst case bound
A General Approximation Technique for Constrained Forest Problems
Approximation schemes for covering and packing problems in image processing and VLSI
The hardness of approximation
Approximation algorithms for NP-hard problems
Approximation of <italic>k</italic>-set cover by semi-local optimization
Improved performance of the greedy algorithm for partial cover
The LovMYAMPERSAND#225;sz Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
Using homogenous weights for approximating the partial cover problem
Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs
New approaches to covering and packing problems
Algorithms for facility location problems with outliers
Computational Complexity of Machine Learning
Approximating k-Set Cover and Complementary Graph Coloring
Approximation Algorithms for Partial Covering Problems
Massaging a Linear Programming Solution to Give a 2-Approximation for a Generalization of the Vertex Cover Problem
The t-Vertex Cover Problem
Improved Approximation Algorithms for the Partial Vertex Cover Problem
Distributions on Level-Sets with Applications to Approximation Algorithms

--CTR
Daniel Golovin , Viswanath Nagarajan , Mohit Singh, Approximating the k-multicut problem, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.621-630, January 22-26, 2006, Miami, Florida
Asaf Levin , Danny Segev, Partial multicuts in trees, Theoretical Computer Science, v.369 n.1-3, p.384-395, December, 2006
Asaf Levin , Danny Segev, Partial multicuts in trees, Theoretical Computer Science, v.369 n.1, p.384-395, 15 December 2006
Qingchun Ren , Qilian Liang, Energy and quality aware query processing in wireless sensor database systems, Information Sciences: an International Journal, v.177 n.10, p.2188-2205, May, 2007
vertex cover;approximation algorithms;primal-dual methods;set cover;partial covering;randomized rounding