CS 787: Advanced Algorithms

Greedy Approximations
Instructor: Dieter van Melkebeek

Approximation algorithms give a solution to a problem in polynomial time, at most a given

factor away from the correct solution. This lecture covers Greedy Approximation Algorithms, in
the context of the Vertex Cover, Metric k-Center, and Set Cover problems.

1 Vertex Cover
A vertex cover of a graph is a set of vertices that “covers” the edges of the graph. That is, every
edge has at least one endpoint in the covering set, or, equivalently, for every vertex, it is either in
the set or adjacent to some vertex which is in the set.
Given: Graph G = (V, E)
Goal: Find a vertex cover of minimum size.

1.1 Approximation algorithm

We first give the definition of matching.

Definition 1 (Matching). Given a graph G = (V, E), a subset of the edges M ⊆ E is a matching
if no two edges of M share an endpoint. A matching of maximum number of edges is called a
maximum matching. A maximal matching is one that cannot be extended by adding another edge.
(A maximum matching is maximal but the reverse is not always true).

We observe the following two facts:

1. OP TV C ≥ |M |, for any matching M in G.

This is so because any vertex cover has to pick at least one endpoint of each edge in the
matching, otherwise this edge would be uncovered.
S
2. For any maximal matching M , S = (u,v)∈M {u, v} is a VC.
Assume it is not a VC. That means there is some edge e = (u, v) ∈ E left uncovered by the
vertices in S. Then neither u or v is an endpoint of any edge in M and thus M could legally
be extended by adding edge e. Thus M is not maximal and we have a contradiction, so S
must be a VC. This also directly implies that OP TV C ≤ |S|.

So we have OP TV C ≤ |S| = 2|M | ≤ 2OP TV C .

Theorem 1. Vertex Cover problem can be approximated to within factor of 2.

Proof. We can use a greedy algorithm to construct a maximal matching M , then by the above two
facts, we have |S| ≤ 2OP TV C , where S is the set of vertices matched in M .

1
1.2 Can the approximation guarantee be improved?
We need to answer the following questions.

Q1: Is “OP TV C ≤ 2|M |” tight?

Yes. Let K2n+1 be a complete graph of 2n + 1 vertices. Then every maximal matching M has
n edges and the vertex cover problem for K2n+1 also has optimal solution with OP T = 2n.
So this is a factor 2 approximation with tight bound. For other graphs, we might be able to
improve the factor, for example, bipartite graphs have a factor 1 approximation.

Q2: Is the analysis of the algorithm tight, i.e., |S| ≤ 2OP TV C ?

Yes. For example, a complete bipartite graph on n + n vertices has OP TV C = n, while the
maximal matchings have |M | = n so |S| = 2|M | = 2n.

Q3: Is the theorem tight?

We do not know! But by assuming reasonable complexity theoretic hypothesis, the answer is
yes.

2 (Metric) k-Center
Given the locations of customers, the problem is to decide on the locations of at most k warehouses
such that the maximum travel time over all the customers is minimized. We can define the problem
formally as follows:
Given:

• Complete (di)graph G = (V, E)

• Weights on the edges, d : E → [0, ∞)

• k∈N

Goal: Find set C ⊆ V with |C| ≤ k s.t. the following objective is minimized:

max(min(d(v, c)))
v∈V c∈C

C is our set of warehouses in this example, and customers are located at each vertex v ∈ V .
Note that minc∈C (d(v, c)) is the distance of customer v to the nearest warehouse. Then maxv∈V (...)
effectively finds the distance traveled by the customer that must travel the longest to reach any
warehouse. This customer is presumably the unhappiest. The overall goal is to then minimize the
maximum unhappiness.
Note that the problem in that original version, called k-center problem, is an NP-complete
problem. Moreover, k-center cannot even be approximated (i.e. it cannot be solved efficiently
to within any constant factor of the optimal objective). So, we consider the problem with the
restriction that d is a metric on V .

Definition 2 (Metric). A function d : X × X → R is a metric on the set X iff (∀x, y, z ∈ X),

2
 d(x, x) = 0
d(x, y) = d(y, x)
d(x, z) ≤ d(x, y) + d(y, z)

2.1 Factor 2 approximation algorithm

We begin with a useful claim.
Claim 1. Within any set of k + 1 vertices, there is some pair, u, v, s.t. d(u, v) ≤ 2OP T .
Proof. Since there are k +1 vertices, and only k centers (in the optimal solution to metric k-center),
the pigeonhole principle tells us that at least two points must be associated with the same center.
Let the vertices be u and v and the shared center be c. Because c is a center, and d is a metric, we
have the following:

d(u, v) ≤ d(u, c) + d(c, v)

≤ 2OP T

This is also depicted in Figure 1. Two vertices which share a center are not farther than 2OP T
because of the triangle inequality inherent in a metric function.

” OPT

” 2 OPT

” OPT

Figure 1: Graphical example for the proof

3
 Now we can present the algorithm. The metric version of k-center problem can be approximated
by greedily selecting the customer who is furthest from any warehouse at each step, and putting
the next warehouse at their location.
Algorithm 1: Metric k-center Greedy Algorithm
(1) if k ≥ |V |
(2) return V
(3) Pick c1 arbitrarily
(4) for i=2 to k
(5) ci ← argmaxv∈V (minj=1,..,i−1 (d(v, cj )))
(6) return C

Claim 2. The algorithm gives a factor 2 approximation.

Proof. Take any vertex v that is not selected by the end of this algorithm’s execution. Consider
this v along with the k selected vertices in C and also let cv ← argminc∈C (d(v, c)).
By Claim 1, we know that some pair of vertices in this group must have distance between them
≤ 2OP T .

• Case 1: v is one of the pair. Because d(v, cv ) ≤ d(v, c)(∀c ∈ C), we know that d(v, cv ) ≤
2OP T .

• Case 2: v is not one of the pair. Then the pair is ci and cj , (i < j) (those vertices selected on
iterations i and j in the algorithm). Because on iteration j, cj was selected in favor of v, we
have the following:

d(v, cv ) ≤ minc∈c1 ,..,cj−1 (d(v, c))

≤ minc∈c1 ,..,cj−1 (d(cj , c))
≤ d(cj , ci )
≤ 2OP T

The selection of v was arbitrary, so we know that any vertex not in C will have minimum distance to
some c ∈ C that is at most a factor of 2 from the optimal unhappiest-customer’s best distance.

2.2 Tightness example

Now, let’s look over the tight example below that shows us the extreme case resulting in the factor
of 2 exactly.
Example: Consider the metric k-center problem for the graph seen in the Figure 2 for k = 1.
Suppose that all the spokes are assigned d = 1 whereas all the other edges are assigned d = 2.
(The figure does not have all these edges but only some of them to prevent a crowding of lines). In
this case, observe that OP T = 1 (just pick the center vertex). The algorithm is likely to pick one
of the other vertices, however, and hence ALG = 2OP T . 

4
 Figure 2: Tightness example for the k-center problem

2.3 Better approximation?

Question: Can we come up with a better factor than 2? Answer: No. (Unless P = NP)

Theorem 2. For any  > 0, metric k-center problem is not approximable within a factor of (2 − )
unless P = NP.

Proof. We will translate an instance of vertex cover (VC) into an instance of the k-center problem.
Remember the VC problem is to determine for a given graph G = (V, E) whether there is a set of
vertices with size at most k such that all vertices are either in the set or adjacent to a vertex in
the set by an edge in G. Given instance (G = (V, E), k) of VC, we construct an instance (G0 , d0 ) of
metric k-center problem (G0 , d0 ) as follows:

1. G0 ← G

2. Remove isolated vertices (those with no edges) from G0

3. Make G0 a complete graph by adding all missing edges

4. Define metric d0 for each edge e

(
0 1 if e ∈ E
d (e) =
2 if e ∈
/E

This is a polynomial time construction. Further, this construction would allow us to distinguish
yes and no cases for VC in polynomial time by running a factor (2 − ) approximation algorithm
for metric k-center on (G0 , d0 ). This is because if G has a vertex cover of size at most k, then
OP T (G0 ) = 1, otherwise OP T (G0 ) = 2.
Suppose algorithm A is a factor (2−) approximation algorithm for the metric k-center problem.

OP T (G0 ) = 1 ⇒ V al(A(G0 )) ≤ (2 − )
OP T (G0 ) = 2 ⇒ V al(A(G0 )) ≥ 2

These are easily distinguishable cases, so if such an algorithm A exists, P = NP.

5
3 Set Cover
In the Set Cover problem, we have a bunch of items which we want to cover, and several sets, each
covering some number of items, and each with a cost to take up the set. The goal is to cover all
items, taking up the the minimum cost selection of sets to do so.
Given:

• Universe U = [m]

• S1 , S2 , .., Sn ⊆ U

• w1 , w2 , .., wn ∈ [0, ∞)

Goal: Find set I ⊆ [n] s.t.

[
Si = U, and
i∈I
X
wi is minimized
i∈I

Note that the requirement of positive weights is not a limitation. If we do have negative weights,
to minimize the total weight we should choose all the subsets with negative weights. Then, we
remove the elements in those subsets from the universe. Finally, it becomes a Set Cover problem
with non-negative weights.
In fact, Set Cover can be seen as a generalization of Vertex Cover. To reduce Vertex Cover to
Set Cover, let U be the set of edges, Si be the set of edges that connect node i to another node,
and wi = 1. This is a restricted version of Set Cover. The subsets are unweighted; i.e., all weigh
the same. Also, f ≡ maxuj ∈U |{i : uj ∈ Si }| = 2, because an edge has exactly 2 endpoints.
For this restricted version of Set Cover, we can directly apply the greedy algorithm for Vertex
Cover, which gives a factor of 2 approximation. In general, if we relax f to be any number, the
greedy technique of Vertex Cover will give us a factor f approximation. However, if there is any
element that is in every subset, then f = m and we gain nothing from the approximation.

3.1 Factor (1 + ln m) approximation algorithm

A greedy algorithm for Set Cover is presented below. The idea is to keep adding subsets that have
minimum marginal cost per new element covered until all elements in U are covered.

Algorithm 2: Set Cover Greedy Algorithm

(1) C←∅
(2) I←∅
(3) while C 6= U
(4) Pick i ∈ [n] s.t. |Si ∩ C| > 0 and |S w∩C|
i
is minimized
i
(5) I ← I ∪ {i}
(6) C ← C ∪ Si
(7) return I

6
Theorem 3.PThe greedy algorithm for Set Cover is an approximation algorithm with factor Hm ,
where Hm = m 1
j=1 j .
Proof. Let u1 , u2 , ..., um be the order in which elements of U are added to C (This ordering is
important for the following proof). We define P rice(uj ) to be the marginal cost per element at the
time uj is added, i.e.
wi
P rice(uj ) = |Si ∩C|
at the time uj is added.
P Pm
Note that Cost(I) = i∈I wi = j=1 P rice(uj ).
OP T
Claim 3. At the time uj is covered, P rice(uj ) ≤ |C|
, where OP T denotes the cost of an optimal
solution.
To see this, note that there is an optimal cover, IOP T . If we knew IOP T , then we could select all
at once those i in IOP T that are not yet in I for extra cost no greater than OP T . Selecting these
optimal sets would yield an average P rice for the elements in C of no more than OP T
|C|
. Because
the minimum value in a group must be no more than the average value in the group, there must be
some set in this optimal selection which alone would cover one or more elements at P rice no more
than OP T
|C|
. Since the P rice for a set cannot decrease over time, and our algorithm selects the set
with minimum P rice, we know that this bound is achieved.
Claim 4. At the time uj is covered, |C| ≥ m − j + 1.
Let uj 0 be the “first” of the elements covered in the iteration in which it is covered. This means
that the number covered so far is |C| = (j 0 − 1), and we also have j ≥ j 0 , so

|C| = |U | − |C|
= m − (j 0 − 1)
= m − j0 + 1
≥m−j+1
By Claim 3 and Claim 4, we have

m
X
Cost(Solution) = P rice(uj )
j=1
m
X OP T
≤
m−j+1
j=1
 
m
X 1
=  OP T
j
j=1

= (Hm )OP T (Hm : mth harmonic number)

≤ (1 + ln m)OP T

Rm Rm 1
Note that ( 1 x1 dx) ≤ ( m 1
P
j=1 j ) ≤ (1 + 1 x dx). Thus, ln n ≤ Hn ≤ 1 + ln n.

7
3.2 Tightness example
Is the analysis of the algorithm tight? The answer is yes. The following is an example.
1
Example: Let S1 = {u1 }, S2 = {u2 }, ..., Sm = {um }, Sm+1 = {u1 , u2 , ..., um }, wi = m−i+1 (for i =
1..m), and wm+1 = 1 + . The optimal solution is to choose Sm+1 alone, which gives OP T = 1 + .
On the other hand, the approximation algorithm will choose S1 , S2 , ..., Sm and the cost is Hm .