Approximate Algorithms (chap. 35)Vertex-cover problemSlide 3Approximate RatioApproximate vertex-cover algorithmExample of approximate vertex-cover2-approximate vertex-coverAnother kind of approximate algorithmAlgorithms1Approximate Algorithms (chap. 35)•Motivation:–Many problems are NP-complete, so unlikely find efficient algorithms–Three ways to get around:•If input size is small, exponential algorithm is OK.•Isolate important special case and find poly algorithms for them.•Find near-optimal solutions in poly time. •So approximate algorithms:–An algorithm returning a near-optimal solution is called approximate algorithm.2Vertex-cover problem•Vertex cover: given an undirected graph G=(V,E), then a subset V'V such that if (u,v)E, then uV' or v V' (or both).•Size of a vertex cover: the number of vertices in it.•Vertex-cover problem: find a vertex-cover of minimal size.3Vertex-cover problem•Vertex-cover problem is NP-complete. (See section 34.5.2).–Vertex-cover belongs to NP.–Vertex-cover is NP-hard (CLIQUEPvertex-cover.)•Reduce <G,k> where G=<V,E> of a CLIQUE instance to <G',|V|-k> where G'=<V,E'> where E'={(u,v): u,vV, uv and <u,v> E} of a vertex-cover instance.•So find an approximate algorithm.4Approximate Ratio•C* is the cost of optimal solution and C is the cost of an approximate algorithm(n)=max(C/C*, C*/C) where n is size of problem input•If (n)=1, then the algorithm is an optimal algorithm•The larger (n), the worse the algorithm5Approximate vertex-cover algorithm6Example of approximate vertex-cover72-approximate vertex-cover•Theorem 35.1 (page 1026).–APPROXIMATE-VERTEX-COVER is a poly time 2-approximate algorithm, i.e., the size of returned vertex cover set is at most twice of the size of optimal vertex-cover.•Proof:–It runs in poly time–The returned C is a vertex-cover.–Let A be the set of edges picked in line 4 and C* be the optimal vertex-cover.•Then C* must include at least one end of each edge in A and no two edges in A are covered by the same vertex in C*, so |C*||A|. •Moreover, |C|=2|A|, so |C|2|C*|.8Another kind of approximate algorithm•Approximate string matching (also called string matching allowing errors):–Find all the substrings in text T that are close to pattern P. –Edit distance: P is said to be of distance k to a string Q if P can be transformed to Q with k following character operations: insertion, deletion, and substitution.–May have other operations and different operations have different costs.–Refer to the handout paper by Sun Wu and Udi Manber.9Algorithms•Sequential•Parallel•Approximate•deterministic•Random•Probabilistic•Genetic–Evolution and