DNA and Nucleotide University of Texas at Dallas达拉斯的核酸和核苷酸.ppt

zek ze1 Ze2 Subset Interconnection Design Given m subsets X1, …, Xm of set X, find a graph G with vertex set X and minimum number of edges such that for every i=1, …, m, the subgraph G[Xi] induced by Xi is connected. fi For any edge set E, define fi(E) to be the number of connected components of the subgraph of (X,E), induced by Xi. Function -fi is submodular. Rank All acyclic subgraphs form a matroid. The rank of a subgraph is the cardinality of a maximum independent subset of edges in the subgraph. Let Ei = {(u,v) in E | u, v in Xi}. Rank ri(E)=ri(Ei)=|Xi|-fi(E). Rank ri is sumodular. Potential Function r1+???+rm Theorem Subset Interconnection Design has a (1+ln m)-approximation. r1(Φ)+???+rm(Φ)=0 r1(e)+???+rm(e)m for any edge Connected Vertex-Cover Given a connected graph, find a minimum vertex-cover which induces a connected subgraph. For any vertex subset A, p(A) is the number of edges not covered by A. For any vertex subset A, q(A) is the number of connected component of the subgraph induced by A. -p is submodular. -q is not submodular. |E|-p(A) p(A)=|E|-p(A) is # of edges covered by A. p(A)+p(B)-p(A U B) = # of edges covered by both A and B p(A ∩ B) -p-q -p-q is submodular. Theorem Connected Vertex-Cover has a (1+ln Δ)-approximation. -p(Φ)=-|E|, -q(Φ)=0. |E|-p(x)-q(x) Δ-1 Δ is the maximum degree. Theorem Connected Vertex-Cover has a 3-approximation. Weighted Connected Vertex-Cover Given a vertex-weighted connected graph, find a connected vertex-cover with minimum total weight. Theorem Weighted Connected Vertex-Cover has a (1+ln Δ)-approximation. This is the best-possible!!! End Thanks! Lecture 23 Greedy Strategy What is a submodular function? Consider a function f on all subsets of a set E. f is submodular if Set-Cover Given a collection C of subsets of a set E, find a minimum subcollection C’ of C such that every element of E appears in a subset in C’ . Example of Submodular Function Greedy Algorithm An