Introduction to algorithms and it's different types

Types of different algorithms

1. Approximation Algorithms
Chapter 1-Introduction

2. My T. Thai
[email protected]
2
General Information
Time: MWF 1:55 –2:45
Place: TUR 2303

3. My T. Thai
[email protected]
3
Instructor Information
Name: Dr. My T. Thai
Office: E566 CSE Building
Phone: [phone]
Email: [email protected]
Office Hours: W 3:00pm –5:00pm or by
appointments

4. My T. Thai
[email protected]
4
Why Approximation Algorithms
Problems that we cannot find an optimal
solution in a polynomial time
Eg: Set Cover, Bin Packing
Need to find a near-optimal solution:
Heuristic
Approximation algorithms:
This gives us a guarantee approximation ratio

5. My T. Thai
[email protected]
5
Why take this course
Your advisers/bosses give you a
computationally hard problem. Here are two
scenarios:
No knowledge about approximation:
Spend a few months looking for an optimal solution
Come to their office and confess that you cannot do it
Get fired
Knowledge about approximation:

6. My T. Thai
[email protected]
6
Why take this course (cont)
Knowledge about approximation
Show your boss that this is a NP-complete (NP-
hard) problem
There does not exist any polynomial time algorithm
to find an exact solution
Propose a good algorithm (either heuristic or
approximation) to find a near-optimal solution
Better yet, prove the approximation ratio

7. My T. Thai
[email protected]
7
Course Description
Covers a variety of techniques to design and
analyze many approximation algorithms for
computationally hard problems:
Combinatorial algorithms:
Greedy Techniques, Independent System, Submodular
Function
Cover various problems
Linear Programming based algorithms
Semidefinite Programming based algorithms

8. My T. Thai
[email protected]
8
Course Objectives
Grasp the essential techniques to design and
analyze approximation algorithms:
Combinatorial methods
Linear programming
Semidefinite programming
Primal-dual and relaxation methods
Hardness of approximation
Grasp the key ideas of graph theory
Able to model and solve many practical
problems raising in our real life

9. My T. Thai
[email protected]
9
Textbooks
Required:
Vijay Vazirani, Approximation Algorithms,
Springer-Verlag, 2001
Recommended:
Vasek Chvatal, Linear Programming, W. H.
Freeman Company
Michael R. Garey and David S. Johnson,
Computers and Intractability: A Guide to the
Theory of NP-Completeness
Shall provide some appropriate lecture notes

10. My T. Thai
[email protected]
10
Grading Policies
Homework Assignments:
5 homework assignments, each weighs 10%
Due at the beginningof the lecture on the due date
No lateassignment will be accepted
Midterm Exam:
One midterm exam,weighs 20%
In class, open book, open notes
One Final Exam:
Weighs 30%

11. My T. Thai
[email protected]
11
Grading Policies (cont)
Cut-off points:
A >= 85%
85% > B >= 75%
75% > C >= 65%

12. My T. Thai
[email protected]
12
Plagiarism Policy
Zero tolerance
Collaboration:
May discuss with other students on homework, but
must write up solution on your own independently
More info, see the class website
Other policy: Students are encouraged to attend
the class. Many proofs will not be shown on the
lecture slides

13. My T. Thai
[email protected]
13
Tentative Schedule
See the class website for detail information
Roughly divided into two parts:
Week 1 to Week 8: Combinatorial Algorithms
Week 9 to Week 16: Linear Programming: Dual-
Primal, Relaxation, Rounding, and Semidefinite
programming

14. My T. Thai
[email protected]
14
Introduction to Combinatorial
Optimization

15. My T. Thai
[email protected]
15
Combinatorial Optimization
The study of finding the “best” object from
within some finite space of objects, eg:
Shortest path: Given a graph with edge costs and a
pair of nodes, find the shortest path (least costs)
between them
Traveling salesman: Given a complete graph with
nonnegative edge costs, find a minimum cost cycle
visiting every vertex exactly once
Maximum Network Lifetime:Given a wireless
sensor networks and a set of targets, find a schedule
of these sensors to maximize network lifetime

16. My T. Thai
[email protected]
16
In P or not in P?
Informal Definitions:
The class P consists of those problems that are
solvable in polynomial time, i.e. O(n
k
)for some
constant kwherenis the size of the input.
The class NP consists of those problems that
are “verifiable” in polynomial time:
Given a certificate of a solution, then we can verify
that the certificate is correct in polynomial time

17. My T. Thai
[email protected]
17
In P or not in P: Examples
In P:
Shortest path
Minimum Spanning Tree
Not in P (NP):
Vertex Cover
Traveling salesman
Minimum Connected Dominating Set

18. My T. Thai
[email protected]
18
NP-completeness (NPC)
A problem is in the class NPC if it is in NP and
is as “hard” as any problem in NP

19. My T. Thai
[email protected]
19
What is “hard”
Decision Problems:Only consider YES-NO
Decision version of TSP: Given n cities, is there a
TSP tour of length at most L?
Why Decision Problem? What relation between
the optimization problem and its decision?
Decision is not “harder” than that of its
optimization problem
If the decision is “hard”, then the optimization
problem should be “hard”

20. My T. Thai
[email protected]
20
NP-complete and NP-hard
A language L is NP-complete if:
1.L is in NP, and
2.For every L’ in NP, L’ can be polynomial-time
reducible to L

21. My T. Thai
[email protected]
21
Approximation Algorithms
An algorithm that returns near-optimal
solutions in polynomial time
Approximation Ratio ρ(n):
Define: C* as a optimal solution and C is the
solution produced by the approximation algorithm
max (C/C*, C*/C) <= ρ(n)
Maximization problem: 0 < C <= C*, thus C*/C
shows that C* is larger than C by ρ(n)
Minimization problem: 0 < C* <= C, thus C/C*
shows that C is larger than C* by ρ(n)

22. My T. Thai
[email protected]
22
Approximation Algorithms (cont)
PTAS (Polynomial Time Approximation
Scheme): A (1 + ε)-approximationalgorithm
for a NP-hard optimization Пwhere its running
time is bounded by a polynomialin the size of
instance I
FPTAS (Fully PTAS): The same as above +
time is bounded by a polynomial in both the
size of instance Iand 1/ε

23. My T. Thai
[email protected]
23
A Dilemma!
We cannot find C*, how can we compare C to
C*?
How can we design an algorithm so that we can
compare C to C*
It is the objective of this course!!!

24. My T. Thai
[email protected]
24
Vertex Cover
Definition:
An Example'at incident endpoint one
leastat has , edgeevery for iff ofcover vertex a
called is 'subset a ,),(graph undirectedan Given
V
eEeG
VVEVG



25. My T. Thai
[email protected]
25
Vertex Cover Problem
Definition:
Given an undirected graph G=(V,E), find a vertex
cover with minimum size (has the least number of
vertices)
This is sometimes called cardinality vertex cover
More generalization:
Given an undirected graph G=(V,E), and a cost
function on vertices c: V →Q+
Find a minimum cost vertex cover

26. My T. Thai
[email protected]
26
How to solve it
Matching:
A set Mof edges in a graph Gis called a matching
of Gif no two edges in set Mhave an endpoint in
common
Example:

27. My T. Thai
[email protected]
27
How to solve it (cont)
Maximum Matching:
A matching of G with the greatest number of edges
Maximal Matching:
A matching which is not contained in any larger
matching
Note: Any maximum matching is certainly
maximal, but not the reverse

28. My T. Thai
[email protected]
28
Main Observation
No vertex can cover two edges of a matching
The size of every vertex cover is at least the
size of every matching: |M| ≤ |C|
|M| = |C| indicates the optimality
Possible Solution: Using Maximal matching to
find Minimum vertex cover

29. My T. Thai
[email protected]
29
An Algorithm
Alg 1: Find a maximal matching in G and output the
set of matched vertices
Theorem: The algorithm 1 is a factor 2-approximation
algorithm.
Proof:optC
MCoptM
Copt
2|| Therefore,
||2|| and ||
:have We1. algorithm from obtainedcover vertex
ofset a be Let solution. optimalan of size a be Let



30. My T. Thai
[email protected]
30
Can Alg1 be improved?
Q1: Can the approximation ratio of Alg 1 be
improved by a better analysis?
Q2: Can we design a better approximation
algorithm using the similar technique (maximal
matching)?
Q3: Is there any other lower bounding method
that can lead to a better approximation
algorithm?

31. My T. Thai
[email protected]
31
Answers
A1: No by considering the complete bipartite
graphs K
n,n
A2: No by considering the complete graph K
n
where n is odd.
|M| = (n-1)/2 whereas opt = n -1

32. My T. Thai
[email protected]
32
Answers (cont)
A3:
Currently a central open problem
Yes, we can obtain a better one by using the
semidefinite programming
Generalization vertex Cover
Can we still able to design a 2-approximation
algorithm?
Homework assignment!

33. My T. Thai
[email protected]
33
Set Cover
Definition: Given a universe Uof nelements, a
collection of subsets of U, S = {S
1, …, S
m}, and a cost
function c: S→ Q+,find a minimum cost
subcollection Cof S that covers all elements of U.
Example:
U = {1, 2, 3, 4, 5}
S
1= {1, 2, 3}, S
2= {2,3}, S
3= {4, 5}, S
4= {1, 2, 4}
c
1= c
2= c
3= c
4 = 1
Solution C = {S
1, S
3}
If the cost is uniform, then the set cover problem asks
us to find a subcollection covering all elements of U
with the minimum size.

34. My T. Thai
[email protected]
34
An Example

35. My T. Thai
[email protected]
35
INSTANCE: Given a universe Uof nelements, a collection
of subsets of U, S = {S
1, …, S
m}, and a positive integer b
QUESTION: Is there a , |C| ≤ b,
such that
(Note: The subcollection {S
i| } satisfying the above
condition is called a set cover of U
NP-completeness
Theorem:Set Cover (SC) is NP-complete
Proof:

36. My T. Thai
[email protected]
36
Proof (cont)
First we need to show that SC is in NP. Given a
collection of sets C, it is easy to verify that if
|C| ≤ band the union of all sets listed in Cdoes
include all elements in U.
To complete the proof, we need to show that
Vertex Cover (VC) ≤
pSet Cover (SC)
Given an instance Cof VC (an undirected graph
G=(V,E) and a positive integer j), we need to
construct an instance C’of SC in polynomial
time such that Cis satisfiable iff C’is
satisfiable.

37. My T. Thai
[email protected]
37
Proof (cont)
Construction:Let U = E. We will define n
elements of U and a collection Sas follows:
Note:Each edge corresponds to each element in U and
each vertex corresponds to each set in S.
Label all vertices in V from 1 to n. Let S
ibe the set of all
edges that incident to vertex i.Finally, let b = j. This
construction is in poly-time with respect to the size of
VC instance.

38. My T. Thai
[email protected]
38
VERTEX-COVER 
pSET-COVER
one set for every vertex,
containing the edges it covers
VC
one element
for every edge
VC SC

39. My T. Thai
[email protected]
39
Proof (cont)
Now, we need to prove that C is satisfiable iff C’ is.
That is, we need to show that if the original instance
of VC is a yes instance iff the constructed instance of
SC is a yes instance.
(→) Suppose G has a vertex cover of size at most j,
called C. By our construction, Ccorresponds to a
collection C’of subsets of U. Since b = j, |C’| ≤ b.
Plus, C’ covers all elements in Usince C “covers” all
edges in G. To see this, consider any element of U.
Such an element is an edge in G. Since C is a set cover,
at least endpoint of this edge is in C.

40. My T. Thai
[email protected]
40
(←) Suppose there is a set cover C’of size at
most b in our constructed instance. Since each
set in C’is associated with a vertex in G, let C
be the set of these vertices. Then |C| = |C’| ≤ b =
j. Plus, C is a vertex cover of G since C’ is a set
cover. To see this, consider any edge e. Since e
is in U, C’must contain at least one set that
includes e. By our construction, the only set
that include e correspond to nodes that are
endpoints of e. Thus Cmust contain at least one
endpoints of e.

41. My T. Thai
[email protected]
41
Solutions
Algorithm 1: (in the case of uniform cost)
1: C= empty
2: whileU is not empty
3:pick a set S
isuch that S
icovers the most
elementsin U
4:remove the new covered elements from U
5:C= Cunion S
i
6: returnC

42. My T. Thai
[email protected]
42
Solutions (cont)
In the case of non-uniform cost
Similar method. At each iteration, instead of picking a
set S
isuch that S
icovers the most uncovered elements,
we will pick a set S
iwhose cost-effectiveness αis
smallest, where αisdefined as:
Questions: Why choose smallest α? Why define αas
above||/)( USSc
ii 

43. My T. Thai
[email protected]
43
Solutions (cont)
Algorithm 2: (in the case of non-uniform cost)
1: C= empty
2: whileU is not empty
3:pick a set S
isuch that S
ihas the smallest α
4: for each new covered elements e in U
5: setprice(e) = α
6:remove the new covered elements from U
7:C= Cunion S
i
8: returnC

44. My T. Thai
[email protected]
44
Approximation Ratio Analysis
Let e
k, k = 1…n, be the elements of U in the order in which
they were covered by Alg 2. We have:
Lemma 1:
Proof: Let U
jbe the set the remaining set Uat iteration j.
That is, U
jcontains all the uncovered elements at
iteration j. At any iteration j, the leftover sets of the
optimal solution can cover the remaining elements at a
cost of at most opt. (Why?)solution optimal theofcost theis where
)1/()(price },,...,1{each For
opt
knoptenk
k


45. My T. Thai
[email protected]
45
Proof of Lemma 1 (cont)
Thus, among these leftover sets, there must exist
one set where its αvalue is at most opt/|U
j|. Let
e
kbe the element covered at this iteration, |Uj| ≥
n–k+ 1. Since e
kwas covered by the most
cost-effective set in this iteration, we have:
price(e
k) ≤ opt/|U
j| ≤ opt/(n-k+1)

46. My T. Thai
[email protected]
46
Approximation Ratio
Theorem 1: The set cover obtained form Alg 2
(also Alg 1) has a factor of H
nwhere H
nis a
harmonic series H
n= 1 + 1/2 + … + 1/n
Proof: It follows directly from Lemma 1