高级算法 (Fall 2016)/Greedy and Local Search

Under construction. 

Set cover

Given a family of sets [math]\displaystyle{ \mathcal{F}=\{S_1,S_2,\ldots,S_n\}\subseteq 2^{U} }[/math] where every member [math]\displaystyle{ S_i\in\mathcal{F} }[/math] in the family is a subset of a universe [math]\displaystyle{ U }[/math], a set cover is a sub-collection [math]\displaystyle{ \mathcal{C}\subseteq\mathcal{F} }[/math] such that [math]\displaystyle{ U=\bigcup_{S\in\mathcal{C}}S }[/math], that is, [math]\displaystyle{ \mathcal{C} }[/math] is a sub-collection of sets whose union "covers" all elements in the universe.

Set Cover Problem

Input: a number of sets [math]\displaystyle{ S_1,S_2,\ldots,S_n }[/math] with the universe [math]\displaystyle{ U=\bigcup_{i=1}^nS_i }[/math]; Output: the smallest [math]\displaystyle{ C\subseteq\{1,2,\ldots,n\} }[/math] such that [math]\displaystyle{ U=\bigcup_{i\in C}S_i }[/math].

Given an undirected graph [math]\displaystyle{ G(U,V) }[/math], a vertex cover is a subset [math]\displaystyle{ C\subseteq V }[/math] of vertices such that every edge [math]\displaystyle{ uv\in E }[/math] has at least one endpoint in [math]\displaystyle{ C }[/math].