Jhoirene Clemente, profile picture
Uploaded byJhoirene Clemente
PDF, PPTX5,572 views

Introduction to Approximation Algorithms

The document discusses approximation algorithms for solving hard combinatorial optimization problems. It defines optimization problems and covers NP-hard problems like the clique, independent set, vertex cover, and traveling salesman problems. Approaches for solving NP-hard problems include exact algorithms, approximation algorithms that provide guaranteed good solutions, and heuristics without guarantees. Approximation algorithms aim to settle for good enough solutions rather than optimal ones.

Science◦
In this document
Powered by AI

Overview of Approximation Algorithms in optimization problems by Jhoirene B Clemente.

Introduction to combinatorial optimization problems, NP-hard problems, and classifications.

Introduction to NP-hard problems including Clique and Max Clique problem with definitions.

Definition of the Max Independent Set Problem and the NP-hard nature of Independent Set.

Definition of the Min Vertex Cover Problem and its classification as NP-hard.

Definition of the Traveling Salesman Problem (TSP) as finding the minimum cost Hamiltonian cycle.

Various approaches such as exact, approximation, and heuristic algorithms to solve NP-hard problems.

Definition of approximation algorithms, properties, and types based on minimization and maximization.

Explanation of approximation ratios in the context of minimization and maximization problems.

Detailed definitions related to Vertex Cover problem and its structure.

Definition of matchings in graphs and introduction of a 2-approximation algorithm for the vertex cover.

Proof and example to demonstrate the efficiency of the 2-approximation algorithm for vertex cover.

Steps to solve TSP, including constructing a minimum spanning tree.

Process of constructing the Hamiltonian cycle using a preorder walk and analyzing tour costs.

Definitions for approximable problems, polynomial-time approximation schemes, and complexity classes.Discussion on MAX SNP problems and the limits of polynomial-time approximation schemes.

Download as PDF, PPTX
Approximation Algorithms Jhoirene B Clemente Algorithms and Complexity Lab Department of Computer Science University of the Philippines Diliman October 14, 2014
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. Combinatorial Optimization Problems 2. NP-Hard Problems 2.1 Clique 2.2 Independent Set Problem 2.3 Vertex Cover 2.4 Traveling Salesman Problem 3. Approaches in Solving Hard Problems 4. Approximation Algorithms 5. Approximable Problems 6. Inapproximable Problems
50 Approximation Algorithms Jhoirene B Clemente 3 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 Optimization Problems [Papadimitriou and Steiglitz, 1998] Definition (Instance of an Optimization Problem) An instance of an optimization problem is a pair (F, c), where F is any set, the domain of feasible points; c is the cost function, a mapping c : F ! R The problem is to find an f 2 F for which c(f ) c(y) 8 y 2 F Such a point f is called a globally optimal solution to the given instance, or, when no confusion can arise, simply an optimal solution.
50 Approximation Algorithms Jhoirene B Clemente 3 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 Optimization Problems [Papadimitriou and Steiglitz, 1998] Definition (Instance of an Optimization Problem) An instance of an optimization problem is a pair (F, c), where F is any set, the domain of feasible points; c is the cost function, a mapping c : F ! R The problem is to find an f 2 F for which c(f ) c(y) 8 y 2 F Such a point f is called a globally optimal solution to the given instance, or, when no confusion can arise, simply an optimal solution. Definition (Optimization Problem) An optimization problem is a set of instances of an optimization problem.
50 Approximation Algorithms Jhoirene B Clemente 4 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 Optimization Problems [Papadimitriou and Steiglitz, 1998] Two categories 1. with continuous variables, where we look for a set of real numbers or a function 2. with discrete variables, which we call combinatorial, where we look for an object from a finite, or possibly countably infinite set, typically an integer, set, permutation, or graph.
50 Approximation Algorithms Jhoirene B Clemente 5 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 Combinatorial Optimization Problem Definition (Combinatorial Optimization Problem [Papadimitriou and Steiglitz, 1998]) An optimization problem = (D,R, cost, goal) consists of 1. A set of valid instances D. Let I 2 D, denote an input instance. 2. Each I 2 D has a set of feasible solutions, R(I ). 3. Objective function, 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. Either minimization or maximization problem: goal 2 {min, max}.
50 Approximation Algorithms Jhoirene B Clemente Optimization Problems 6 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 NP-Hard Problems 1. Clique Problem 2. Independent Set Problem 3. Vertex Cover Problem 4. Traveling Salesman Problem
50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems 7 Clique 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 Problem Definition (Max Clique Problem) Given a complete weighted graph, find the largest clique
50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems 7 Clique 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 Problem Definition (Max Clique Problem) Given a complete weighted graph, find the largest clique Theorem Max Clique is NP-hard [Garey and Johnson, 1979].
50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems 7 Clique 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 Problem Definition (Max Clique Problem) Given a complete weighted graph, find 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].
50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems 8 Clique 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)
50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems 9 Clique 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
50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique 10 Independent Set Problem Vertex Cover Approaches in Solving Hard Problems Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Independent Set Definition (Max Independent Set Problem) Given a complete weighted graph, find the largest independent set
50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique 10 Independent Set Problem Vertex Cover Approaches in Solving Hard Problems Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Independent Set Definition (Max Independent Set Problem) Given a complete weighted graph, find the largest independent set Theorem Independent Set Problem is NP-hard [Garey and Johnson, 1979].
50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique Independent Set Problem 11 Vertex Cover Approaches in Solving Hard Problems Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Vertex Cover Problem Definition (Min Vertex Cover Problem) Given a complete weighted graph, find the minimum vertex cover.
50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique Independent Set Problem 11 Vertex Cover Approaches in Solving Hard Problems Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Vertex Cover Problem Definition (Min Vertex Cover Problem) Given a complete weighted graph, find the minimum vertex cover. Theorem Vertex Cover Problem is NP-hard [Garey and Johnson, 1979].
50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique Independent Set Problem 12 Vertex Cover Approaches in Solving Hard Problems Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Traveling Salesman Problem (TSP) Definition INPUT: Edge weighted Graph G = (V,E) OUTPUT: Minimum cost Hamiltonian Cycle.
50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique Independent Set Problem Vertex Cover 13 Approaches in Solving Hard Problems Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Approaches in Solving NP-hard Problems I Exact algorithm always obtain the optimal solution I Approximation algorithm settle for good enough solutions. Goodness of solution is guaranteed and measured using approximation ratio. I Heuristic algorithms produce solutions, which are not guaranteed to be close to the optimum. The performance of heuristics is often evaluated empirically.
50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique Independent Set Problem Vertex Cover 14 Approaches 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 have a well specified structure that even provides a framework for possible implementations Concepts formulate ideas and rough frameworks about how to attack hard algorithmic problems .
50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique Independent Set Problem Vertex Cover 14 Approaches 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 have a well specified structure that even provides a framework for possible implementations I Dynamic Programming I Greedy Schema I Divide and conquer I Branch and Bound I Local search I . . . Concepts formulate ideas and rough frameworks about how to attack hard algorithmic problems . I Approximation Algorithms I Parameterized Algorithms I Randomized Algorithms I . . .
50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique Independent Set Problem Vertex Cover Approaches in Solving Hard Problems 15 Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Approximation Algorithms Definition (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 of of the value of an optimal solution. Given an problem instance I with an optimal solution Opt(I ), i.e. the cost function cost(Opt(I )) is minimum/maximum.
50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique Independent Set Problem Vertex Cover Approaches in Solving Hard Problems 15 Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Approximation Algorithms Definition (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 of of the value of an optimal solution. Given an problem instance I with an optimal solution Opt(I ), i.e. the cost function cost(Opt(I )) is minimum/maximum. I An algorithm for a minimization problem is called -approximative algorithm for some 1, if the algorithm obtains a maximum cost of · cost(Opt(I )), for any input instance I .
50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique Independent Set Problem Vertex Cover Approaches in Solving Hard Problems 15 Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Approximation Algorithms Definition (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 of of the value of an optimal solution. Given an problem instance I with an optimal solution Opt(I ), i.e. the cost function cost(Opt(I )) is minimum/maximum. I An algorithm for a minimization problem is called -approximative algorithm for some 1, if the algorithm obtains a maximum cost of · cost(Opt(I )), for any input instance I . I An algorithm for a maximization problem is called -approximative algorithm, for some 1, if the algorithm obtains a minimum cost of · cost(Opt(I )), for any input instance I .
50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique Independent Set Problem Vertex Cover Approaches in Solving Hard Problems 16 Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Approximation Ratio I Minimization, 1 cost(Opt(I )) cost(SOL) cost(Opt(I )) I Maximization, 1 cost(Opt(I )) cost(SOL) cost(Opt(I ))
50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique Independent Set Problem Vertex Cover Approaches in Solving Hard Problems 17 Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Approximation Ratio I Additive Approximation Algorithms: SOL OPT + c I Constant Approximation Algorithms: SOL c · OPT I Logarithmic Approximation Algorithms: SOL = O(log n) · OPT I Polynomial Approximation Algorithms: SOL = O(nc) · OPT, where c 1
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 18 Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Example: Vertex Cover Problem Definition (Vertex Cover [Vazirani, 2001] ) Given a graph G = (V,E), a vertex cover is a subset C V such that every edge has at least one end point incident at C.
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 18 Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Example: Vertex Cover Problem Definition (Vertex Cover [Vazirani, 2001] ) Given a graph G = (V,E), a vertex cover is a subset C V such that every edge has at least one end point incident at C.
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 18 Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Example: Vertex Cover Problem Definition (Vertex Cover [Vazirani, 2001] ) Given a graph G = (V,E), a vertex cover is a subset C V such that every edge has at least one end point incident at C. Definition (Minimum Vertex Cover Problem) Given a complete weighted graph G = (V,E), find a minimum cardinality vertex cover C.
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 19 Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Maximal Matching Definition (Matchings) Given a graph G = (V,E), a subset M E is called a matching if no two edges in M are adjacent in G. Figure : (a) Maximal matching (b) Perfect matching
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 20 Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 2-Approximation Algorithm 1. Find a maximal matching in G, and output the set of matched vertices. Algorithm 1: 2-Approximation Algorithm for minimum vector cover problem
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 21 Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 2-Approximation Algorithm Theorem Algorithm 1 is a 2-approximation algorithm.
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 21 Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 2-Approximation Algorithm Theorem Algorithm 1 is a 2-approximation algorithm. Proof. Let M be a maximal matching in G = (V,E) and OPT be the minimum vertex cover in G, then |M| |OPT| The cover picked by the algorithm has cardinality |SOL| 2 · |M|. |SOL| 2 · |OPT|
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 22 Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 2-Approximation Algorithm Example:
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 22 Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 2-Approximation Algorithm Example:
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 23 Traveling Salesman Problem References CS 397 October 14, 2014 Solving Traveling Salesman Problem INPUT: Edge weighted graph 1. Compute a Minimum Spanning Tree for G 2. Select a vertex r 2 V(G) to be the root vertex 3. Let L be the list of vertices visited in a preorder walk OUTPUT: Hamiltonian Cycle that visits A preorder tree walk recursively visits every vertex in the tree, listing a vertex when it is first encountered , before any of its children are visited.
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 24 Traveling Salesman Problem References CS 397 October 14, 2014 Computing the Minimum Spanning Tree
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 25 Traveling Salesman Problem References CS 397 October 14, 2014 Computing the Minimum Spanning Tree
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 26 Traveling Salesman Problem References CS 397 October 14, 2014 Computing the Minimum Spanning Tree
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 27 Traveling Salesman Problem References CS 397 October 14, 2014 Computing the Minimum Spanning Tree
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 28 Traveling Salesman Problem References CS 397 October 14, 2014 Computing the Minimum Spanning Tree
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 29 Traveling Salesman Problem References CS 397 October 14, 2014 Computing the Minimum Spanning Tree
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 30 Traveling Salesman Problem References CS 397 October 14, 2014 Computing the Minimum Spanning Tree
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 31 Traveling Salesman Problem References CS 397 October 14, 2014 Computing the Minimum Spanning Tree
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 32 Traveling Salesman Problem References CS 397 October 14, 2014 Computing the Minimum Spanning Tree
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 33 Traveling Salesman Problem References CS 397 October 14, 2014 Computing the Minimum Spanning Tree
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 34 Traveling Salesman Problem References CS 397 October 14, 2014 Computing the Minimum Spanning Tree
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 35 Traveling Salesman Problem References CS 397 October 14, 2014 Preorder
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 36 Traveling Salesman Problem References CS 397 October 14, 2014 Preorder
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 37 Traveling Salesman Problem References CS 397 October 14, 2014 Preorder
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 38 Traveling Salesman Problem References CS 397 October 14, 2014 Preorder
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 39 Traveling Salesman Problem References CS 397 October 14, 2014 Preorder
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 40 Traveling Salesman Problem References CS 397 October 14, 2014 Preorder
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 41 Traveling Salesman Problem References CS 397 October 14, 2014 Preorder
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 42 Traveling Salesman Problem References CS 397 October 14, 2014 Hamiltonian Cycle from the Preorder Walk
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 43 Traveling Salesman Problem References CS 397 October 14, 2014 Hamiltonian Cycle from the Preorder Walk 4 + 4 + 10 + 15 + 10 + 16 = 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 44 Traveling Salesman Problem References CS 397 October 14, 2014 Total tour cost vs. the optimal cost Let H denote an optimal Hamiltonian tour in G. Let T be the minimum spanning tree of G. c(T) c(H) Let W be 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)
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 44 Traveling Salesman Problem References CS 397 October 14, 2014 Total tour cost vs. the optimal cost Let H denote an optimal Hamiltonian tour in G. Let T be the minimum spanning tree of G. c(T) c(H) Let W be 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 () is 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 45 Traveling Salesman Problem References CS 397 October 14, 2014 Approximable Problems [Vazirani, 2001] Definition (APX) I An abbreviation for “Approximable, is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant.
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 45 Traveling Salesman Problem References CS 397 October 14, 2014 Approximable Problems [Vazirani, 2001] Definition (APX) I An abbreviation for “Approximable, is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant. I Problems in this class have efficient algorithms that can find an answer within some fixed percentage of the optimal answer.
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 46 Traveling Salesman Problem References CS 397 October 14, 2014 Polynomial-time Approximation Schemes Definition (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 find a solution whose cost is within a 1 + factor of the optimum cost. Contains FPTAS, and is contained in APX.
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 46 Traveling Salesman Problem References CS 397 October 14, 2014 Polynomial-time Approximation Schemes Definition (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 find a solution whose cost is within a 1 + factor of the optimum cost. Contains FPTAS, and is contained in APX. Definition (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 find a solution whose cost is within a 1 + factor of the optimum cost. Furthermore, the running time of the algorithm is polynomial in n (the size of the problem) and in 1/.
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 47 Traveling Salesman Problem References CS 397 October 14, 2014 Approximation Ratio of well known Hard Problems 1. FPTAS: Bin Packing Problem 2. PTAS: Makespan Scheduling Problem 3. APX: 3.1 Min Steiner Tree Problem (1.55 Approximable) [Robins,2005] 3.2 Min Metric TSP (3/2 Approximable) [Christofides,1977] 3.3 Max SAT (0.77 Approximable) [Asano,1997] 3.4 Vertex Cover (2 Approximable) [Vazirani,2001] 4. MAX SNP 4.1 Independent Set Problem 4.2 Clique Problem 4.3 Travelling Salesman Problem
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 48 Traveling Salesman Problem References CS 397 October 14, 2014 Complexity Classes [Ausiello et al., 2011] FPTAS ( PTAS ( APX ( NPO
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 49 Traveling 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].
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 49 Traveling 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].
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 49 Traveling 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 If P6= NP, then for any constant 1, there is no polynomial-time approximation algorithm with approximation ratio for the general travelling salesman problem.
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 50 References CS 397 October 14, 2014 References I Aaronson, S., Kuperberg, G., and Granade, C. (2008). The complexity zoo.

More Related Content

PPT
Randomized algorithms ver 1.0
byDr. C.V. Suresh Babu
 
PPTX
2_1 Edit Distance.pptx
bytanishamahajan11
 
PPT
Dynamic pgmming
byDr. C.V. Suresh Babu
 
PPTX
Np hard
byjesal_joshi
 
PPTX
Presentation of daa on approximation algorithm and vertex cover problem
bysumit gyawali
 
PPTX
Asymptotic Notation
byProtap Mondal
 
PPT
SINGLE-SOURCE SHORTEST PATHS
byMd. Shafiuzzaman Hira
 
PPTX
Randomized Algorithm
byKanishka Khandelwal
 
Randomized algorithms ver 1.0
byDr. C.V. Suresh Babu
 
2_1 Edit Distance.pptx
bytanishamahajan11
 
Dynamic pgmming
byDr. C.V. Suresh Babu
 
Np hard
byjesal_joshi
 
Presentation of daa on approximation algorithm and vertex cover problem
bysumit gyawali
 
Asymptotic Notation
byProtap Mondal
 
SINGLE-SOURCE SHORTEST PATHS
byMd. Shafiuzzaman Hira
 
Randomized Algorithm
byKanishka Khandelwal
 

What's hot

PDF
9. chapter 8 np hard and np complete problems
byJyotsna Suryadevara
 
PDF
Approximation Algorithms
byNicolas Bettenburg
 
PPTX
Bruteforce algorithm
byRezwan Siam
 
PPTX
daa-unit-3-greedy method
byhodcsencet
 
PPTX
Compiler: Syntax Analysis
byDr. Jaydeep Patil
 
PDF
Daa notes 1
bysmruti sarangi
 
PPTX
Divide and Conquer - Part 1
byAmrinder Arora
 
PPTX
Introduction to Dynamic Programming, Principle of Optimality
byBhavin Darji
 
PPTX
Knapsack Problem
byJenny Galino
 
PDF
P, NP, NP-Complete, and NP-Hard
byAnimesh Chaturvedi
 
PDF
Ch 7 Knowledge Representation.pdf
byKrishnaMadala1
 
PDF
Daa notes 2
bysmruti sarangi
 
PPTX
Traveling salesman problem
byJayesh Chauhan
 
PDF
Loop invarient
byAmit Kumar Rathi
 
PPTX
Vertex cover Problem
byGajanand Sharma
 
PPT
finding Min and max element from given array using divide & conquer
bySwati Kulkarni Jaipurkar
 
PPT
01 knapsack using backtracking
bymandlapure
 
PPTX
Brute force-algorithm
by9854098540
 
PPTX
Backtracking-N Queens Problem-Graph Coloring-Hamiltonian cycle
byvarun arora
 
PPT
Graph colouring
byPriyank Jain
 
9. chapter 8 np hard and np complete problems
byJyotsna Suryadevara
 
Approximation Algorithms
byNicolas Bettenburg
 
Bruteforce algorithm
byRezwan Siam
 
daa-unit-3-greedy method
byhodcsencet
 
Compiler: Syntax Analysis
byDr. Jaydeep Patil
 
Daa notes 1
bysmruti sarangi
 
Divide and Conquer - Part 1
byAmrinder Arora
 
Introduction to Dynamic Programming, Principle of Optimality
byBhavin Darji
 
Knapsack Problem
byJenny Galino
 
P, NP, NP-Complete, and NP-Hard
byAnimesh Chaturvedi
 
Ch 7 Knowledge Representation.pdf
byKrishnaMadala1
 
Daa notes 2
bysmruti sarangi
 
Traveling salesman problem
byJayesh Chauhan
 
Loop invarient
byAmit Kumar Rathi
 
Vertex cover Problem
byGajanand Sharma
 
finding Min and max element from given array using divide & conquer
bySwati Kulkarni Jaipurkar
 
01 knapsack using backtracking
bymandlapure
 
Brute force-algorithm
by9854098540
 
Backtracking-N Queens Problem-Graph Coloring-Hamiltonian cycle
byvarun arora
 
Graph colouring
byPriyank Jain
 

Similar to Introduction to Approximation Algorithms

PDF
Reoptimization techniques for solving hard problems
byJhoirene Clemente
 
PDF
DeepLearn2022 1. Goals & AlgorithmDesign.pdf
bySean Meyn
 
PDF
A Regularized Simplex Method
byGina Brown
 
PDF
Reoptimization Algorithms and Persistent Turing Machines
byJhoirene Clemente
 
PPT
Analysis of Algorithm
byأحلام انصارى
 
PDF
Introduction to optimization Problems
byElectronics & Communication Staff SCU Suez Canal University
 
PDF
Low Rank Optimisation, by Irène Waldspurger
byParis Women in Machine Learning and Data Science
 
PPT
Introduction to Optimization revised.ppt
byJahnaviGautam
 
PDF
LP linear programming (summary) (5s)
byDionísio Carmo-Neto
 
PPT
Primal Dual
bycarlol
 
PPTX
Basic presentation of convex optimization 2018.pptx
byubaidqureshi27
 
DOCX
Mb0048 operations research
bysmumbahelp
 
PPTX
Approximation
byRiyaSingh235
 
PDF
Fine Grained Complexity
byAkankshaAgrawal55
 
PPT
Support Vector Machines
bynextlib
 
PPT
Primal Dual
bycarlol
 
PPT
Approx
byguest0264d3b
 
PDF
Molodtsov's Soft Set Theory and its Applications in Decision Making
byinventionjournals
 
PDF
Molodtsov's Soft Set Theory and its Applications in Decision Making
byinventionjournals
 
PDF
Boyd 4.6, 4.7
byKoki Isokawa
 
Reoptimization techniques for solving hard problems
byJhoirene Clemente
 
DeepLearn2022 1. Goals & AlgorithmDesign.pdf
bySean Meyn
 
A Regularized Simplex Method
byGina Brown
 
Reoptimization Algorithms and Persistent Turing Machines
byJhoirene Clemente
 
Analysis of Algorithm
byأحلام انصارى
 
Introduction to optimization Problems
byElectronics & Communication Staff SCU Suez Canal University
 
Low Rank Optimisation, by Irène Waldspurger
byParis Women in Machine Learning and Data Science
 
Introduction to Optimization revised.ppt
byJahnaviGautam
 
LP linear programming (summary) (5s)
byDionísio Carmo-Neto
 
Primal Dual
bycarlol
 
Basic presentation of convex optimization 2018.pptx
byubaidqureshi27
 
Mb0048 operations research
bysmumbahelp
 
Approximation
byRiyaSingh235
 
Fine Grained Complexity
byAkankshaAgrawal55
 
Support Vector Machines
bynextlib
 
Primal Dual
bycarlol
 
Approx
byguest0264d3b
 
Molodtsov's Soft Set Theory and its Applications in Decision Making
byinventionjournals
 
Molodtsov's Soft Set Theory and its Applications in Decision Making
byinventionjournals
 
Boyd 4.6, 4.7
byKoki Isokawa
 

Recently uploaded

PPTX
liquids2-211104045137 ftgv здравствуйтк до
bymrcody389
 
PPTX
tracheostomy .pptx
byNagaMalya
 
PPTX
Transgenic Animal Technology (Animal biotechnology)
bysagrooumr
 
PDF
Bioactivity Data : Binding database and DrugBank
bySree
 
PPTX
IN SITU CONSERVATION(introduction, aim and objectives, types, monitoring and ...
byRASHMI M G
 
PDF
s13613-024-01355-6 jurnal terkait imun.pdf
byMuhammadSuyadi2
 
PDF
Near the Runaway: The Climate and Habitability of Teegarden’s Star b
bySérgio Sacani
 
PPTX
tracheostomy .pptx
byNagaMalya
 
PPTX
Material Cycling Powerpoint Presentation.pptx
byMariannJoyTanilon1
 
PDF
MedComm - 2024 - Wang - The interaction of innate immune and adaptive immune ...
byMuhammadSuyadi2
 
PPT
1.2 THE MOLE CONCEPT.PPT relationships with mole concept
bysunitha671758
 
PPTX
presentationbiotechnologyandgeneticengineering-210822163345.pptx
byduaaalwakeel5
 
PPTX
PHARMACOLOGYhhgjiiuhkouhk9ijjuokhikkijiok
byMyatThandar9
 
PDF
Lectures on Fourier Series (Exploring Harmonic Analysis)
byPranav Sharma
 
PDF
The scientific heritage No 170 (170) (2025)
byThe scientific heritage
 
PDF
Rotkotoe_ The EUREKA - Simple Explanation.pdf
byRotko Rotko Toe
 
PDF
Understanding Work and Organisation. PDF
byNokwandaNzuza2
 
PDF
Rotkotoe_ The EUREKA - Complete Manuscript.pdf
byRotko Rotko Toe
 
PPTX
A Step-by-Step Guide - Calculating Water Hardness with EDTA Titration
byLearnbin
 
PPTX
Design Pattern Slide 03aaaaaaaaaaaaaaaaaaa.pptx
bynrezaeeof
 
liquids2-211104045137 ftgv здравствуйтк до
bymrcody389
 
tracheostomy .pptx
byNagaMalya
 
Transgenic Animal Technology (Animal biotechnology)
bysagrooumr
 
Bioactivity Data : Binding database and DrugBank
bySree
 
IN SITU CONSERVATION(introduction, aim and objectives, types, monitoring and ...
byRASHMI M G
 
s13613-024-01355-6 jurnal terkait imun.pdf
byMuhammadSuyadi2
 
Near the Runaway: The Climate and Habitability of Teegarden’s Star b
bySérgio Sacani
 
tracheostomy .pptx
byNagaMalya
 
Material Cycling Powerpoint Presentation.pptx
byMariannJoyTanilon1
 
MedComm - 2024 - Wang - The interaction of innate immune and adaptive immune ...
byMuhammadSuyadi2
 
1.2 THE MOLE CONCEPT.PPT relationships with mole concept
bysunitha671758
 
presentationbiotechnologyandgeneticengineering-210822163345.pptx
byduaaalwakeel5
 
PHARMACOLOGYhhgjiiuhkouhk9ijjuokhikkijiok
byMyatThandar9
 
Lectures on Fourier Series (Exploring Harmonic Analysis)
byPranav Sharma
 
The scientific heritage No 170 (170) (2025)
byThe scientific heritage
 
Rotkotoe_ The EUREKA - Simple Explanation.pdf
byRotko Rotko Toe
 
Understanding Work and Organisation. PDF
byNokwandaNzuza2
 
Rotkotoe_ The EUREKA - Complete Manuscript.pdf
byRotko Rotko Toe
 
A Step-by-Step Guide - Calculating Water Hardness with EDTA Titration
byLearnbin
 
Design Pattern Slide 03aaaaaaaaaaaaaaaaaaa.pptx
bynrezaeeof
 

Introduction to Approximation Algorithms

  • 1.
    Approximation Algorithms JhoireneB 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. Combinatorial Optimization Problems 2. NP-Hard Problems 2.1 Clique 2.2 Independent Set Problem 2.3 Vertex Cover 2.4 Traveling Salesman Problem 3. Approaches in Solving Hard Problems 4. Approximation Algorithms 5. Approximable Problems 6. Inapproximable Problems
  • 3.
    50 Approximation Algorithms Jhoirene B Clemente 3 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 Optimization Problems [Papadimitriou and Steiglitz, 1998] Definition (Instance of an Optimization Problem) An instance of an optimization problem is a pair (F, c), where F is any set, the domain of feasible points; c is the cost function, a mapping c : F ! R The problem is to find an f 2 F for which c(f ) c(y) 8 y 2 F Such a point f is called a globally optimal solution to the given instance, or, when no confusion can arise, simply an optimal solution.
  • 4.
    50 Approximation Algorithms Jhoirene B Clemente 3 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 Optimization Problems [Papadimitriou and Steiglitz, 1998] Definition (Instance of an Optimization Problem) An instance of an optimization problem is a pair (F, c), where F is any set, the domain of feasible points; c is the cost function, a mapping c : F ! R The problem is to find an f 2 F for which c(f ) c(y) 8 y 2 F Such a point f is called a globally optimal solution to the given instance, or, when no confusion can arise, simply an optimal solution. Definition (Optimization Problem) An optimization problem is a set of instances of an optimization problem.
  • 5.
    50 Approximation Algorithms Jhoirene B Clemente 4 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 Optimization Problems [Papadimitriou and Steiglitz, 1998] Two categories 1. with continuous variables, where we look for a set of real numbers or a function 2. with discrete variables, which we call combinatorial, where we look for an object from a finite, or possibly countably infinite set, typically an integer, set, permutation, or graph.
  • 6.
    50 Approximation Algorithms Jhoirene B Clemente 5 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 Combinatorial Optimization Problem Definition (Combinatorial Optimization Problem [Papadimitriou and Steiglitz, 1998]) An optimization problem = (D,R, cost, goal) consists of 1. A set of valid instances D. Let I 2 D, denote an input instance. 2. Each I 2 D has a set of feasible solutions, R(I ). 3. Objective function, 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. Either minimization or maximization problem: goal 2 {min, max}.
  • 7.
    50 Approximation Algorithms Jhoirene B Clemente Optimization Problems 6 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 NP-Hard Problems 1. Clique Problem 2. Independent Set Problem 3. Vertex Cover Problem 4. Traveling Salesman Problem
  • 8.
    50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems 7 Clique 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 Problem Definition (Max Clique Problem) Given a complete weighted graph, find the largest clique
  • 9.
    50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems 7 Clique 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 Problem Definition (Max Clique Problem) Given a complete weighted graph, find the largest clique Theorem Max Clique is NP-hard [Garey and Johnson, 1979].
  • 10.
    50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems 7 Clique 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 Problem Definition (Max Clique Problem) Given a complete weighted graph, find 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 8 Clique 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 9 Clique 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 10 Independent Set Problem Vertex Cover Approaches in Solving Hard Problems Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Independent Set Definition (Max Independent Set Problem) Given a complete weighted graph, find the largest independent set
  • 14.
    50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique 10 Independent Set Problem Vertex Cover Approaches in Solving Hard Problems Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Independent Set Definition (Max Independent Set Problem) Given a complete weighted graph, find 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 11 Vertex Cover Approaches in Solving Hard Problems Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Vertex Cover Problem Definition (Min Vertex Cover Problem) Given a complete weighted graph, find the minimum vertex cover.
  • 16.
    50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique Independent Set Problem 11 Vertex Cover Approaches in Solving Hard Problems Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Vertex Cover Problem Definition (Min Vertex Cover Problem) Given a complete weighted graph, find 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 12 Vertex Cover Approaches in Solving Hard Problems Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Traveling Salesman Problem (TSP) Definition INPUT: Edge weighted Graph G = (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 13 Approaches in Solving Hard Problems Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Approaches in Solving NP-hard Problems I Exact algorithm always obtain the optimal solution I Approximation algorithm settle for good enough solutions. Goodness of solution is guaranteed and measured using approximation ratio. I Heuristic algorithms produce solutions, which are not guaranteed to be close to the optimum. The performance of heuristics is often evaluated empirically.
  • 19.
    50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique Independent Set Problem Vertex Cover 14 Approaches 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 have a well specified structure that even provides a framework for possible implementations Concepts formulate ideas and rough frameworks about how to attack hard algorithmic problems .
  • 20.
    50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique Independent Set Problem Vertex Cover 14 Approaches 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 have a well specified structure that even provides a framework for possible implementations I Dynamic Programming I Greedy Schema I Divide and conquer I Branch and Bound I Local search I . . . Concepts formulate ideas and rough frameworks about how to attack hard algorithmic problems . I Approximation Algorithms I Parameterized Algorithms I Randomized Algorithms I . . .
  • 21.
    50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique Independent Set Problem Vertex Cover Approaches in Solving Hard Problems 15 Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Approximation Algorithms Definition (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 of of the value of an optimal solution. Given an problem instance I with an optimal solution Opt(I ), i.e. the cost function cost(Opt(I )) is minimum/maximum.
  • 22.
    50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique Independent Set Problem Vertex Cover Approaches in Solving Hard Problems 15 Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Approximation Algorithms Definition (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 of of the value of an optimal solution. Given an problem instance I with an optimal solution Opt(I ), i.e. the cost function cost(Opt(I )) is minimum/maximum. I An algorithm for a minimization problem is called -approximative algorithm for some 1, if the algorithm obtains a maximum cost of · cost(Opt(I )), for any input instance I .
  • 23.
    50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique Independent Set Problem Vertex Cover Approaches in Solving Hard Problems 15 Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Approximation Algorithms Definition (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 of of the value of an optimal solution. Given an problem instance I with an optimal solution Opt(I ), i.e. the cost function cost(Opt(I )) is minimum/maximum. I An algorithm for a minimization problem is called -approximative algorithm for some 1, if the algorithm obtains a maximum cost of · cost(Opt(I )), for any input instance I . I An algorithm for a maximization problem is called -approximative algorithm, for some 1, if the algorithm obtains a minimum cost of · cost(Opt(I )), for any input instance I .
  • 24.
    50 Approximation Algorithms Jhoirene B Clemente Optimization Problems Hard Combinatorial Optimization Problems Clique Independent Set Problem Vertex Cover Approaches in Solving Hard Problems 16 Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Approximation Ratio I Minimization, 1 cost(Opt(I )) cost(SOL) cost(Opt(I )) I Maximization, 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 17 Approximation Algorithms Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Approximation Ratio I Additive Approximation Algorithms: SOL OPT + c I Constant Approximation Algorithms: SOL c · OPT I Logarithmic Approximation Algorithms: SOL = O(log n) · OPT I Polynomial Approximation Algorithms: SOL = O(nc) · OPT, where c 1
  • 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 18 Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Example: Vertex Cover Problem Definition (Vertex Cover [Vazirani, 2001] ) Given a graph G = (V,E), a vertex cover is a subset C V such that every edge has at least one end point incident at C.
  • 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 18 Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Example: Vertex Cover Problem Definition (Vertex Cover [Vazirani, 2001] ) Given a graph G = (V,E), a vertex cover is a subset C V such that every edge has at least one end point incident at C.
  • 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 18 Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Example: Vertex Cover Problem Definition (Vertex Cover [Vazirani, 2001] ) Given a graph G = (V,E), a vertex cover is a subset C V such that every edge has at least one end point incident at C. Definition (Minimum Vertex Cover Problem) Given a complete weighted graph G = (V,E), find a minimum cardinality vertex cover C.
  • 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 19 Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 Maximal Matching Definition (Matchings) Given a graph G = (V,E), a subset M E is called a matching if no two edges in M are adjacent in G. Figure : (a) Maximal matching (b) Perfect matching
  • 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 20 Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 2-Approximation Algorithm 1. Find a maximal matching in 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 21 Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 2-Approximation Algorithm Theorem Algorithm 1 is a 2-approximation algorithm.
  • 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 21 Vertex Cover Traveling Salesman Problem References CS 397 October 14, 2014 2-Approximation Algorithm Theorem Algorithm 1 is a 2-approximation algorithm. Proof. Let M be a maximal matching in G = (V,E) and OPT be the minimum vertex cover in G, then |M| |OPT| The cover picked by the algorithm has cardinality |SOL| 2 · |M|. |SOL| 2 · |OPT|
  • 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 22 Vertex 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 22 Vertex 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 23 Traveling Salesman Problem References CS 397 October 14, 2014 Solving Traveling Salesman Problem INPUT: Edge weighted graph 1. Compute a Minimum Spanning Tree for G 2. Select a vertex r 2 V(G) to be the root vertex 3. Let L be the list of vertices visited in a preorder walk OUTPUT: Hamiltonian Cycle that visits A preorder tree walk recursively visits every vertex in the tree, listing a vertex when it is first 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 24 Traveling 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 25 Traveling 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 26 Traveling 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 27 Traveling 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 28 Traveling 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 29 Traveling 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 30 Traveling 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 31 Traveling 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 32 Traveling 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 33 Traveling 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 34 Traveling 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 35 Traveling 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 36 Traveling 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 37 Traveling 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 38 Traveling 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 39 Traveling 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 40 Traveling 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 41 Traveling 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 42 Traveling 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 43 Traveling 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 44 Traveling Salesman Problem References CS 397 October 14, 2014 Total tour cost vs. the optimal cost Let H denote an optimal Hamiltonian tour in G. Let T be the minimum spanning tree of G. c(T) c(H) Let W be 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)
  • 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 44 Traveling Salesman Problem References CS 397 October 14, 2014 Total tour cost vs. the optimal cost Let H denote an optimal Hamiltonian tour in G. Let T be the minimum spanning tree of G. c(T) c(H) Let W be 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 () is 2
  • 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 45 Traveling Salesman Problem References CS 397 October 14, 2014 Approximable Problems [Vazirani, 2001] Definition (APX) I An abbreviation for “Approximable, is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant.
  • 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 45 Traveling Salesman Problem References CS 397 October 14, 2014 Approximable Problems [Vazirani, 2001] Definition (APX) I An abbreviation for “Approximable, is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant. I Problems in this class have efficient algorithms that can find an answer within some fixed 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 46 Traveling Salesman Problem References CS 397 October 14, 2014 Polynomial-time Approximation Schemes Definition (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 find a solution whose cost is within a 1 + factor of the optimum cost. Contains FPTAS, and is contained in APX.
  • 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 46 Traveling Salesman Problem References CS 397 October 14, 2014 Polynomial-time Approximation Schemes Definition (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 find a solution whose cost is within a 1 + factor of the optimum cost. Contains FPTAS, and is contained in APX. Definition (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 find a solution whose cost is within a 1 + factor of the optimum cost. Furthermore, the running time of the algorithm is polynomial in n (the size of the problem) and in 1/.
  • 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 47 Traveling Salesman Problem References CS 397 October 14, 2014 Approximation Ratio of well known Hard Problems 1. FPTAS: Bin Packing Problem 2. PTAS: Makespan Scheduling Problem 3. APX: 3.1 Min Steiner Tree Problem (1.55 Approximable) [Robins,2005] 3.2 Min Metric TSP (3/2 Approximable) [Christofides,1977] 3.3 Max SAT (0.77 Approximable) [Asano,1997] 3.4 Vertex Cover (2 Approximable) [Vazirani,2001] 4. MAX SNP 4.1 Independent Set Problem 4.2 Clique Problem 4.3 Travelling Salesman Problem
  • 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 48 Traveling 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 49 Traveling 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].
  • 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 49 Traveling 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].
  • 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 49 Traveling 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 If P6= NP, then for any constant 1, there is no polynomial-time approximation algorithm with approximation ratio for 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 50 References CS 397 October 14, 2014 References I Aaronson, S., Kuperberg, G., and Granade, C. (2008). The complexity zoo.