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

Under construction. 

Set cover

Given a number of subsets [math]\displaystyle{ S_1,S_2,\ldots,S_n\subseteq U }[/math] of a universe [math]\displaystyle{ U }[/math], a [math]\displaystyle{ C\subseteq\{1,2,\ldots,n\} }[/math] forms a set cover if [math]\displaystyle{ U=\bigcup_{i\in\mathcal{C}}S_i }[/math], that is, [math]\displaystyle{ \mathcal{C} }[/math] is a sub-collection of sets whose union "covers" all elements in the universe.

This defines a natural optimization problem:

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].

We can think of each instance as a bipartite graph [math]\displaystyle{ G(U,\{S_1,S_2,\ldots,S_n\}, E) }[/math] with elements [math]\displaystyle{ x\in U }[/math] of the universe on the left side, subsets [math]\displaystyle{ S_1,S_2,\ldots,S_n }[/math] on the right side, and there is a bipartite edge between element [math]\displaystyle{ x }[/math] and set [math]\displaystyle{ S_i }[/math] if and only if [math]\displaystyle{ x\in S_i }[/math]. By this translation the set cover problem is precisely the problem of given as input a bipartite graph [math]\displaystyle{ G(U,V,E) }[/math], to find the smallest subset [math]\displaystyle{ C\subseteq V }[/math] of vertices on the right side to "cover" all vertices on the left side, i.e. every vertex on the left side [math]\displaystyle{ x\in U }[/math] is incident to some vertex in [math]\displaystyle{ C }[/math].

By alternating the roles of sets and elements in the above interpretation of set cover as bipartite cover, the set cover problem can be translated to the following equivalent hitting set problem.

Hitting Set Problem

Input: a number of sets [math]\displaystyle{ S_1,S_2,\ldots,S_m }[/math] with the universe [math]\displaystyle{ U=\bigcup_{i=1}^mS_i }[/math]; Output: the smallest subset [math]\displaystyle{ C\subseteq U }[/math] of elements such that [math]\displaystyle{ C }[/math] intersects with every set [math]\displaystyle{ S_i }[/math] for [math]\displaystyle{ 1\le i\le m }[/math].

Frequency and Vertex Cover

Given an instance of set cover problem [math]\displaystyle{ S_1,S_2,\ldots,S_n\subseteq U }[/math], for every element [math]\displaystyle{ x\in U }[/math], its frequency denoted as [math]\displaystyle{ frequency(x) }[/math] is defined as the number

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].