Approximation Algorithms
Dr. Shams ur Rahman
UET Mardan
By Dr. Shams ur Rahman, UET Mardan
What are approximation algorithms?
• Efficient algorithms that find approximate solutions
• Optimization problems (in particular NP-hard problems)
• Provable guarantees on the distance of the returned solution to
the optimal one
• Approximate solutions should be as close to the optimal solution
as possible.
• Approximation algorithm’s time complexity should be polynomial
time and not too high.
• Approximation algorithms are the last resort when exact
polynomial time solutions cannot be found.
By Dr. Shams ur Rahman, UET Mardan
The vertex cover problem
• Given an undirected graph G = (V, E)
• Find the smallest set of vertices, called a "vertex cover," such that every edge
in the graph is incident to at least one vertex in the set.
• A vertex cover C is a subset of V where, for every edge (u, v) in E , at least
one of u or v belongs to C.
• The objective is to minimize the size of the vertex cover.
• The vertex cover problem is NP-hard
• finding an optimal solution for all instances is computationally challenging.
• Practical Significance
• The vertex cover problem has applications in various fields, including network design,
resource allocation, and optimization.
By Dr. Shams ur Rahman, UET Mardan
The vertex cover problem
• Given an undirected graph G = (V, E)
• Find the smallest set of vertices, called a "vertex cover," such that
every edge in the graph is incident to at least one vertex in the set.
• A vertex cover C is a subset of V where, for every edge (u, v) in E ,
at least one of u or v belongs to C.
• The objective is to minimize the size of the vertex cover.
• The vertex cover problem is NP-hard
• finding an optimal solution for all instances is computationally challenging.
• Practical Significance
• The vertex cover problem has applications in various fields, including
network design, resource allocation, and optimization.
By Dr. Shams ur Rahman, UET Mardan
Graphic: [Link]
The vertex cover problem (Approximation
Algorithm)
• Initialization
• Start with an empty set C (the vertex cover).
• Initialize a set U containing all edges of the graph.
• Greedy Iteration
While U is not empty:
• Choose an arbitrary uncovered edge (u,v).
• Add both vertices u and v to C.
• Remove all edges incident to u and v from U.
• Termination
• When U becomes empty, C is a vertex cover.
By Dr. Shams ur Rahman, UET Mardan
The vertex cover problem (Approximation
Algorithm)
• Initialization a b
• Start with an empty set C (the vertex cover).
• Initialize a set U containing all edges of the graph.
• Greedy Iteration c
e
While U is not empty:
• Choose an arbitrary uncovered edge (u,v).
• Add both vertices u and v to C. d
• Remove all edges incident to u and v from U.
f
• Termination g
• When U becomes empty, C is a vertex cover.
h
C = {}
U={(a,b),(a,c),(b,c),(b,e),(c,d),(c,f),(d,e),(d,f),(d,g),(d,h),(e,g)}
By Dr. Shams ur Rahman, UET Mardan
The vertex cover problem (Approximation
Algorithm)
• Initialization a b
• Start with an empty set C (the vertex cover).
• Initialize a set U containing all edges of the graph.
• Greedy Iteration c
e
While U is not empty:
• Choose an arbitrary uncovered edge (u,v).
• Add both vertices u and v to C. d
• Remove all edges incident to u and v from U.
f
• Termination g
• When U becomes empty, C is a vertex cover.
h
C = {b,c}
U={(a,b),(a,c),(b,c),(b,e),(c,d),(c,f),(d,e),(d,f),(d,g),(d,h),(e,g)}
By Dr. Shams ur Rahman, UET Mardan
The vertex cover problem (Approximation
Algorithm)
• Initialization a b
• Start with an empty set C (the vertex cover).
• Initialize a set U containing all edges of the graph.
• Greedy Iteration c
e
While U is not empty:
• Choose an arbitrary uncovered edge (u,v).
• Add both vertices u and v to C. d
• Remove all edges incident to u and v from U.
f
• Termination g
• When U becomes empty, C is a vertex cover.
h
C = {b,c}
U={(a,b),(a,c),(b,c),(b,e),(c,d),(c,f),(d,e),(d,f),(d,g),(d,h),(e,g)}
By Dr. Shams ur Rahman, UET Mardan
The vertex cover problem (Approximation
Algorithm)
• Initialization a b
• Start with an empty set C (the vertex cover).
• Initialize a set U containing all edges of the graph.
• Greedy Iteration c
e
While U is not empty:
• Choose an arbitrary uncovered edge (u,v).
• Add both vertices u and v to C. d
• Remove all edges incident to u and v from U.
f
• Termination g
• When U becomes empty, C is a vertex cover.
h
C = {b,c,d,g}
U={(d,e),(d,f),(d,g),(d,h),(e,g)} By Dr. Shams ur Rahman, UET Mardan
The vertex cover problem (Approximation
Algorithm)
• Initialization a b
• Start with an empty set C (the vertex cover).
• Initialize a set U containing all edges of the graph.
• Greedy Iteration c
e
While U is not empty:
• Choose an arbitrary uncovered edge (u,v).
• Add both vertices u and v to C. d
• Remove all edges incident to u and v from U.
f
• Termination g
• When U becomes empty, C is a vertex cover.
h
C = {b,c,d,g}
U={(d,e),(d,f),(d,g),(d,h),(e,g)} By Dr. Shams ur Rahman, UET Mardan
The vertex cover problem (Approximation
Algorithm)
• Initialization a b
• Start with an empty set C (the vertex cover).
• Initialize a set U containing all edges of the graph.
• Greedy Iteration c
e
While U is not empty:
• Choose an arbitrary uncovered edge (u,v).
• Add both vertices u and v to C. d
• Remove all edges incident to u and v from U.
f
• Termination g
• When U becomes empty, C is a vertex cover.
h
C = {b,c,d,g}
U={} By Dr. Shams ur Rahman, UET Mardan
The vertex cover problem (Approximation
Algorithm)
• Initialization a b
• Start with an empty set C (the vertex cover).
• Initialize a set U containing all edges of the graph.
• Greedy Iteration c
e
While U is not empty:
• Choose an arbitrary uncovered edge (u,v).
• Add both vertices u and v to C. d
• Remove all edges incident to u and v from U.
f
• Termination g
• When U becomes empty, C is a vertex cover.
h
C = {b,c,d,g}
U={} By Dr. Shams ur Rahman, UET Mardan
The vertex cover problem (Approximation
Algorithm)
• It’s a 2-approximation algorithm
• The vertex cover produced ≤ 2*Optimal cover
Proof
• Let C* be the optimal solution (minimum vertex cover)
• Let A be the set of edges chosen randomly by the algorithm
• For each edge (u,v) in A, C* must contain one of its endpoints (u or v)
• No two edges in A share an endpoint
• If none of the endpoints of (u,v) is included in C*, then the edge will not be
covered.
• So the size of C* must be at least half the size of C.
• 1/2|C| ≤ |C*|
• |C| ≤ 2|C*|
By Dr. Shams ur Rahman, UET Mardan
Traveling Salesman Problem
• A salesman has to visit N cities and return.
• Find the shortest possible tour that visits a given set of cities and
returns to the starting city.
• TSP has practical applications in various fields, such as logistics,
manufacturing, and network optimization.
• TSP is NP-hard.
By Dr. Shams ur Rahman, UET Mardan
TSP Approximation Algorithm
• APPROX-TSP-TOUR
• select a vertex r to be a “root” vertex of the graph G
• compute a minimum spanning tree T for G from root r
• Prim’s or Kruskal’s algorithm can be used to compute the MST
• Let H be a list of vertices, ordered according to when they are first
visited in a preorder tree walk of T
• return the Hamiltonian cycle H
By Dr. Shams ur Rahman, UET Mardan
TSP Approximation Algorithm
APPROX-TSP-TOUR
• select a vertex r to be a “root” vertex of
the graph G
• compute a minimum spanning tree T for
G from root r
• Prim’s or Kruskal’s algorithm can be used
to compute the MST
• Let H be a list of vertices, ordered
according to when they are first visited in
a preorder tree walk of T
• return the Hamiltonian cycle H
Graphic taken from Introduction to Algorithms by Thomas H. Cormen,
By Dr. Shams Charles
ur Rahman, E. Leiserson, Ronald L. Rivest, and Clifford Stein.
UET Mardan
TSP Approximation Algorithm
Graphic taken from Introduction to Algorithms by Thomas H. Cormen,
By Dr. Shams Charles
ur Rahman, E. Leiserson, Ronald L. Rivest, and Clifford Stein.
UET Mardan
TSP Approximation Algorithm
• It’s a 2-approximation algorithm
• The length of the tour produced ≤ 2*length of optimal tour
Proof:
• H: produced tour, T*: minimum spanning tree, T: any spanning tree, W: a full walk
• c(T*) ≤ c(T)
• Let H* denote the optimal tour
• Removing an edge from H* results in a spanning tree T’
• Cost of minimum of spanning tree is less than length of H*
• c(T) ≤ c(H*)
• c(T*) ≤ c(H*)
• In a full walk each vertex of the MST is traversed twice
• c(W) ≤ 2c(T*)
• c(W) ≤ 2c(T*) ≤ 2c(H*)
• c(W) ≤ 2c(H*)
• The cost of the tour H (produced by approx. alg.) is not more than the full walk.
• c(H) ≤ c(W)
• c(H) ≤ 2c(H*) By Dr. Shams ur Rahman, UET Mardan
K-center problem
• Given a set of locations (vertices) and
an integer k, find k centers such that the
maximum distance of any location to
its nearest center is minimized.
• Let G=(V,E) be a complete graph with V
representing locations and E
representing edges with associated
distances.
• Find a subset C⊆V of size k such that
maxu∈Vminv∈Cd(u,v) is minimized.
• The problem is NP-hard.
Graphic: [Link]
By Dr. Shams ur Rahman, UET Mardan
K-center problem
• Initialization:
• Select an arbitrary location as the first center.
• Repeat Until k Centers Are Chosen:
• For each location, calculate its distance to the nearest existing center.
• Choose the location with the maximum distance as the new center.
• Termination:
• After selecting k centers, the algorithm concludes.
By Dr. Shams ur Rahman, UET Mardan
More problems
• See the Section 12.3 of the book “Introduction to the Design and
Analysis of Algorithms” for more approximation algorithms.
By Dr. Shams ur Rahman, UET Mardan