Introduction to Approximation Algorithms

Introduction to Approximation Algorithms

1. Approximation Algorithms
Jhoirene B Clemente
Algorithms and Complexity Lab
Department of Computer Science
University of the Philippines Diliman
October 14, 2014

2. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Overview
1.
2.2.1
2.22.32.43.4.5.6.

3. 50
Approximation
Algorithms
Jhoirene B Clemente
3Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Optimization Problems
[Papadimitriou and Steiglitz, 1998]
Denition (Instance of an Optimization Problem)
Aninstance of an optimization problemis a pair(F;c), whereF
is any set, the domain of feasible points;cis the cost function, a
mapping
c:F!R
The problem is to nd anf2Ffor which
c(f)c(y)8y2F
Such a pointfis called aglobally optimalsolution to the given
instance, or, when no confusion can arise, simply anoptimal
solution.
Denition (Optimization Problem)
Anoptimization problemis a set of instances of an optimization
problem.

4. 50
Approximation
Algorithms
Jhoirene B Clemente
3Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Optimization Problems
[Papadimitriou and Steiglitz, 1998]
Denition (Instance of an Optimization Problem)
Aninstance of an optimization problemis a pair(F;c), whereF
is any set, the domain of feasible points;cis the cost function, a
mapping
c:F!R
The problem is to nd anf2Ffor which
c(f)c(y)8y2F
Such a pointfis called aglobally optimalsolution to the given
instance, or, when no confusion can arise, simply anoptimal
solution.
Denition (Optimization Problem)
Anoptimization problemis a set of instances of an optimization
problem.

5. 50
Approximation
Algorithms
Jhoirene B Clemente
4Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Optimization Problems
[Papadimitriou and Steiglitz, 1998]
Two categories
1. continuousvariables, where we look for a set of real
numbers or a function
2. discretevariables, which we call, where
we look for an object from a nite, or possibly countably
innite set, typically an integer, set, permutation, or graph.

6. 50
Approximation
Algorithms
Jhoirene B Clemente
5Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Combinatorial Optimization Problem
Denition (Combinatorial Optimization Problem
[Papadimitriou and Steiglitz, 1998])
An optimization problem = (D;R;cost;goal)consists of
1. D. LetI2 D, denote an input
instance.
2. I2 Dhas a set of feasible solutions,R(I).
3. cost, that assigns a nonnegative
rational number to each pair(I;SOL), where I is an instance
and SOL is a feasible solution to I.
4.
goal2 fmin;maxg.

7. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
6Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
NP-Hard Problems
1.
2.3.4.

8. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
7Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Max Clique ProblemDenition (Max Clique Problem)
Given a complete weighted graph, nd the largest clique
Theorem
Max Clique is NP-hard [Garey and Johnson, 1979].
Proposition
The decision variant of MAX-SAT is NP-Complete
[Garey and Johnson, 1979].

9. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
7Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Max Clique ProblemDenition (Max Clique Problem)
Given a complete weighted graph, nd the largest clique
Theorem
Max Clique is NP-hard [Garey and Johnson, 1979].
Proposition
The decision variant of MAX-SAT is NP-Complete
[Garey and Johnson, 1979].

10. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
7Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Max Clique ProblemDenition (Max Clique Problem)
Given a complete weighted graph, nd the largest clique
Theorem
Max Clique is NP-hard [Garey and Johnson, 1979].
Proposition
The decision variant of MAX-SAT is NP-Complete
[Garey and Johnson, 1979].

11. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
8Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Max Clique Reduction from SAT
Example
(a_b_c)^(b_c_

d)^(a_c_d)^(a_

b_

d)

12. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
9Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Max Clique Reduction from SAT

13. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
10Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Independent SetDenition (Max Independent Set Problem)
Given a complete weighted graph, nd the largest independent set
Theorem
Independent Set Problem is NP-hard [Garey and Johnson, 1979].

14. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
10Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Independent SetDenition (Max Independent Set Problem)
Given a complete weighted graph, nd the largest independent set
Theorem
Independent Set Problem is NP-hard [Garey and Johnson, 1979].

15. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
11Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Vertex Cover ProblemDenition (Min Vertex Cover Problem)
Given a complete weighted graph, nd the minimum vertex cover.
Theorem
Vertex Cover Problem is NP-hard [Garey and Johnson, 1979].

16. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
11Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Vertex Cover ProblemDenition (Min Vertex Cover Problem)
Given a complete weighted graph, nd the minimum vertex cover.
Theorem
Vertex Cover Problem is NP-hard [Garey and Johnson, 1979].

17. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
12Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Traveling Salesman Problem (TSP)
DenitionINPUT: Edge weighted GraphG= (V;E)
OUTPUT: Minimum cost Hamiltonian Cycle.

18. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
13Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Approaches in Solving NP-hard Problems
IExact
IApproximation
Goodness of solution is
approximation ratio.
IHeuristic
guaranteed
heuristics is often evaluated empirically.

19. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
14Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Approaches in Solving NP-hard Problems
Design technique
provides a framework for possible implementations
IDynamic ProgrammingIGreedy SchemaIDivide and conquerIBranch and BoundILocal searchI: : :Concepts
attack hard algorithmic problems .
IApproximation AlgorithmsIParameterized AlgorithmsIRandomized AlgorithmsI: : :

20. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
14Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Approaches in Solving NP-hard Problems
Design technique
provides a framework for possible implementations
IDynamic ProgrammingIGreedy SchemaIDivide and conquerIBranch and BoundILocal searchI: : :Concepts
attack hard algorithmic problems .
IApproximation AlgorithmsIParameterized AlgorithmsIRandomized AlgorithmsI: : :

21. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
15Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Approximation Algorithms
Denition (Approximation Algorithm
[Williamson and Shmoy, 2010] )
An-approximation algorithm for an optimization problem is a
polynomial-time algorithm that for all instances of the problem
produces a solution whose value is within a factor ofof the
value of an optimal solution.
Given an problem instanceIwith an optimal solutionOpt(I), i.e.
the cost functioncost(Opt(I))is minimum/maximum.
IAn algorithm for aminimization problemis called
-approximative algorithm >1, if the algorithm
obtains a cost(Opt(I)), for any input
instanceI.
IAn algorithm for amaximization problemis called
-approximative algorithm, for some <1, if the algorithm
obtains a cost(Opt(I)), for any input
instanceI.

22. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
15Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Approximation Algorithms
Denition (Approximation Algorithm
[Williamson and Shmoy, 2010] )
An-approximation algorithm for an optimization problem is a
polynomial-time algorithm that for all instances of the problem
produces a solution whose value is within a factor ofof the
value of an optimal solution.
Given an problem instanceIwith an optimal solutionOpt(I), i.e.
the cost functioncost(Opt(I))is minimum/maximum.
IAn algorithm for aminimization problemis called
-approximative algorithm >1, if the algorithm
obtains a cost(Opt(I)), for any input
instanceI.
IAn algorithm for amaximization problemis called
-approximative algorithm, for some <1, if the algorithm
obtains a cost(Opt(I)), for any input
instanceI.

23. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
15Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Approximation Algorithms
Denition (Approximation Algorithm
[Williamson and Shmoy, 2010] )
An-approximation algorithm for an optimization problem is a
polynomial-time algorithm that for all instances of the problem
produces a solution whose value is within a factor ofof the
value of an optimal solution.
Given an problem instanceIwith an optimal solutionOpt(I), i.e.
the cost functioncost(Opt(I))is minimum/maximum.
IAn algorithm for aminimization problemis called
-approximative algorithm >1, if the algorithm
obtains a cost(Opt(I)), for any input
instanceI.
IAn algorithm for amaximization problemis called
-approximative algorithm, for some <1, if the algorithm
obtains a cost(Opt(I)), for any input
instanceI.

24. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
16Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Approximation Ratio
IMinimization, >1
cost(Opt(I))cost(SOL)cost(Opt(I))
IMaximization, <1
cost(Opt(I))cost(SOL)cost(Opt(I))

25. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
17Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Approximation Ratio
IAdditive Approximation Algorithms:
SOLOPT+c
IConstant Approximation Algorithms:
SOLcOPT
ILogarithmic Approximation Algorithms:
SOL=O(logn)OPT
IPolynomial Approximation Algorithms:
SOL=O(n
c
)OPT;
wherec1

26. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
18Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Example: Vertex Cover ProblemDenition (Vertex Cover [Vazirani, 2001] )
Given a graphG= (V;E), a vertex cover is a subsetCV
such that every edge has at least one end point incident atC.
Denition (Minimum Vertex Cover Problem)
Given a complete weighted graphG= (V;E), nd a minimum
cardinality vertex coverC.

27. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
18Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Example: Vertex Cover ProblemDenition (Vertex Cover [Vazirani, 2001] )
Given a graphG= (V;E), a vertex cover is a subsetCV
such that every edge has at least one end point incident atC.
Denition (Minimum Vertex Cover Problem)
Given a complete weighted graphG= (V;E), nd a minimum
cardinality vertex coverC.

28. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
18Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Example: Vertex Cover ProblemDenition (Vertex Cover [Vazirani, 2001] )
Given a graphG= (V;E), a vertex cover is a subsetCV
such that every edge has at least one end point incident atC.
Denition (Minimum Vertex Cover Problem)
Given a complete weighted graphG= (V;E), nd a minimum
cardinality vertex coverC.

29. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
19Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
Maximal Matching
Denition (Matchings)
Given a graphG= (V;E), a subsetMEis called a matching
if no two edges inMare adjacent inG.
Figure :

30. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
20Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
2-Approximation Algorithm
1. G, and output the set of
matched vertices.
Algorithm 1:2-Approximation Algorithm for minimum vector
cover problem

31. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
21Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
2-Approximation Algorithm
Theorem
Algorithm 1 is a 2-approximation algorithm.
Proof.
LetMbe a maximal matching inG= (V;E)andOPTbe the
minimum vertex cover inG, then
jMj jOPTj
The cover picked by the algorithm has cardinalityjSOLj 2 jMj.
jSOLj 2 jOPTj

32. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
21Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
2-Approximation Algorithm
Theorem
Algorithm 1 is a 2-approximation algorithm.
Proof.
LetMbe a maximal matching inG= (V;E)andOPTbe the
minimum vertex cover inG, then
jMj jOPTj
The cover picked by the algorithm has cardinalityjSOLj 2 jMj.
jSOLj 2 jOPTj

33. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
22Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
2-Approximation Algorithm
Example:

34. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
22Vertex Cover
Traveling Salesman Problem
References
CS 397
October 14, 2014
2-Approximation Algorithm
Example:

35. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
23Traveling Salesman Problem
References
CS 397
October 14, 2014
Solving Traveling Salesman Problem
INPUT: Edge weighted graph
1.2. r2V(G)to be the root vertex3.
OUTPUT: Hamiltonian Cycle that visits A
tree, listing a vertex when it is rst encountered , before
any of its children are visited.

36. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
24Traveling Salesman Problem
References
CS 397
October 14, 2014
Computing the Minimum Spanning Tree

37. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
25Traveling Salesman Problem
References
CS 397
October 14, 2014
Computing the Minimum Spanning Tree

38. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
26Traveling Salesman Problem
References
CS 397
October 14, 2014
Computing the Minimum Spanning Tree

39. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
27Traveling Salesman Problem
References
CS 397
October 14, 2014
Computing the Minimum Spanning Tree

40. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
28Traveling Salesman Problem
References
CS 397
October 14, 2014
Computing the Minimum Spanning Tree

41. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
29Traveling Salesman Problem
References
CS 397
October 14, 2014
Computing the Minimum Spanning Tree

42. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
30Traveling Salesman Problem
References
CS 397
October 14, 2014
Computing the Minimum Spanning Tree

43. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
31Traveling Salesman Problem
References
CS 397
October 14, 2014
Computing the Minimum Spanning Tree

44. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
32Traveling Salesman Problem
References
CS 397
October 14, 2014
Computing the Minimum Spanning Tree

45. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
33Traveling Salesman Problem
References
CS 397
October 14, 2014
Computing the Minimum Spanning Tree

46. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
34Traveling Salesman Problem
References
CS 397
October 14, 2014
Computing the Minimum Spanning Tree

47. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
35Traveling Salesman Problem
References
CS 397
October 14, 2014
Preorder

48. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
36Traveling Salesman Problem
References
CS 397
October 14, 2014
Preorder

49. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
37Traveling Salesman Problem
References
CS 397
October 14, 2014
Preorder

50. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
38Traveling Salesman Problem
References
CS 397
October 14, 2014
Preorder

51. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
39Traveling Salesman Problem
References
CS 397
October 14, 2014
Preorder

52. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
40Traveling Salesman Problem
References
CS 397
October 14, 2014
Preorder

53. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
41Traveling Salesman Problem
References
CS 397
October 14, 2014
Preorder

54. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
42Traveling Salesman Problem
References
CS 397
October 14, 2014
Hamiltonian Cycle from the Preorder Walk

55. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
43Traveling Salesman Problem
References
CS 397
October 14, 2014
Hamiltonian Cycle from the Preorder Walk
4+4+10+15+10+16=59

56. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
44Traveling Salesman Problem
References
CS 397
October 14, 2014
Total tour cost vs. the optimal cost
LetH

denote an optimal Hamiltonian tour inG. LetTbe the
minimum spanning tree ofG.
c(T)c(H

)
LetWbe the full length cost of the preorder walk.
c(W) =2c(T)
Let H be the output Hamiltonian Cycle from the algorithm
c(W)c(H)
Then
c(H)2c(H

)
Approximation ratio()is2

57. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
44Traveling Salesman Problem
References
CS 397
October 14, 2014
Total tour cost vs. the optimal cost
LetH

denote an optimal Hamiltonian tour inG. LetTbe the
minimum spanning tree ofG.
c(T)c(H

)
LetWbe the full length cost of the preorder walk.
c(W) =2c(T)
Let H be the output Hamiltonian Cycle from the algorithm
c(W)c(H)
Then
c(H)2c(H

)
Approximation ratio()is2

58. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
45Traveling Salesman Problem
References
CS 397
October 14, 2014
Approximable Problems [Vazirani, 2001]
Denition (APX)
IAn abbreviation forApproximable", is the set of NP
optimization problems that allow polynomial-time
approximation algorithms with approximation ratio bounded
by a constant.
IProblems in this class have ecient algorithms that can nd
an answer within some xed percentage of the optimal
answer.

59. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
45Traveling Salesman Problem
References
CS 397
October 14, 2014
Approximable Problems [Vazirani, 2001]
Denition (APX)
IAn abbreviation forApproximable", is the set of NP
optimization problems that allow polynomial-time
approximation algorithms with approximation ratio bounded
by a constant.
IProblems in this class have ecient algorithms that can nd
an answer within some xed percentage of the optimal
answer.

60. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
46Traveling Salesman Problem
References
CS 397
October 14, 2014
Polynomial-time Approximation Schemes
Denition (PTAS [Aaronson et al., 2008])
The subclass of NPO problems that admit an approximation
scheme in the following sense.
For any >0, there is a polynomial-time algorithm that is
guaranteed to nd a solution whose cost is within a1+factor
of the optimum cost. Contains FPTAS, and is contained in APX.
Denition (FPTAS [Aaronson et al., 2008] )
The subclass of NPO problems that admit an approximation
scheme in the following sense.
For any >0, there is an algorithm that is guaranteed to nd a
solution whose cost is within a1+factor of the optimum cost.
Furthermore, the running time of the algorithm is polynomial inn
(the size of the problem) and in1=.

61. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
46Traveling Salesman Problem
References
CS 397
October 14, 2014
Polynomial-time Approximation Schemes
Denition (PTAS [Aaronson et al., 2008])
The subclass of NPO problems that admit an approximation
scheme in the following sense.
For any >0, there is a polynomial-time algorithm that is
guaranteed to nd a solution whose cost is within a1+factor
of the optimum cost. Contains FPTAS, and is contained in APX.
Denition (FPTAS [Aaronson et al., 2008] )
The subclass of NPO problems that admit an approximation
scheme in the following sense.
For any >0, there is an algorithm that is guaranteed to nd a
solution whose cost is within a1+factor of the optimum cost.
Furthermore, the running time of the algorithm is polynomial inn
(the size of the problem) and in1=.

62. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
47Traveling Salesman Problem
References
CS 397
October 14, 2014
Approximation Ratio of well known Hard
Problems
1.
2.3.3.1
3.23.33.4
4.4.1
4.24.3

63. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
48Traveling Salesman Problem
References
CS 397
October 14, 2014
Complexity Classes [Ausiello et al., 2011]
FPTAS(PTAS(APX(NPO

64. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
49Traveling Salesman Problem
References
CS 397
October 14, 2014
Inapproximable Problems
Many problems have polynomial-time approximation schemes.
However, there exists a class of problems that is not so easy
[Williamson and Shmoy, 2010]. This class is called MAX SNP.
Theorem
For any MAXSNP-hard problem, there does not exist a
polynomial-time approximation scheme, unless P = NP
[Williamson and Shmoy, 2010].
Theorem
IfP6=NP, then for any constant1, there is no
polynomial-time approximation algorithm with approximation
ratiofor the general travelling salesman problem.

65. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
49Traveling Salesman Problem
References
CS 397
October 14, 2014
Inapproximable Problems
Many problems have polynomial-time approximation schemes.
However, there exists a class of problems that is not so easy
[Williamson and Shmoy, 2010]. This class is called MAX SNP.
Theorem
For any MAXSNP-hard problem, there does not exist a
polynomial-time approximation scheme, unless P = NP
[Williamson and Shmoy, 2010].
Theorem
IfP6=NP, then for any constant1, there is no
polynomial-time approximation algorithm with approximation
ratiofor the general travelling salesman problem.

66. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
49Traveling Salesman Problem
References
CS 397
October 14, 2014
Inapproximable Problems
Many problems have polynomial-time approximation schemes.
However, there exists a class of problems that is not so easy
[Williamson and Shmoy, 2010]. This class is called MAX SNP.
Theorem
For any MAXSNP-hard problem, there does not exist a
polynomial-time approximation scheme, unless P = NP
[Williamson and Shmoy, 2010].
Theorem
IfP6=NP, then for any constant1, there is no
polynomial-time approximation algorithm with approximation
ratiofor the general travelling salesman problem.

67. 50
Approximation
Algorithms
Jhoirene B Clemente
Optimization Problems
Hard Combinatorial
Optimization Problems
Clique
Independent Set Problem
Vertex Cover
Approaches in Solving
Hard Problems
Approximation
Algorithms
Vertex Cover
Traveling Salesman Problem
50References
CS 397
October 14, 2014
References
Aaronson, S., Kuperberg, G., and Granade, C. (2008).
The complexity zoo.
Ausiello, G., Bonifaci, V., and Escoer, B. (2011).
Complexity and approximation in reoptimization.
InComputability in Context: Computation and Logic in the Real World,
volume 2, pages 101129.
Garey, M. R. and Johnson, D. S. (1979).
Computers and Intractability: A Guide to the Theory of NP-Completeness.
Papadimitriou, C. and Steiglitz, K. (1998).
Combinatorial optimization: algorithms and complexity.
Vazirani, V. V. (2001).
Approximation algorithms, volume 1997.
Williamson, D. and Shmoy, D. (2010).
The Design of Approximation Algorithms.