高级算法 (Fall 2016)/Greedy and Local Search: Difference between revisions
imported>Etone |
imported>Etone |
||
| Line 2: | Line 2: | ||
= Set cover = | = Set cover = | ||
Given a | Given a number of subsets <math>S_1,S_2,\ldots,S_n\subseteq U</math> of a universe <math>U</math>, a <math>C\subseteq\{1,2,\ldots,n\}</math> forms a '''set cover''' if <math>U=\bigcup_{i\in\mathcal{C}}S_i</math>, that is, <math>\mathcal{C}</math> is a sub-collection of sets whose union "covers" all elements in the universe. | ||
This defines a natural optimization problem: | |||
{{Theorem|Set Cover Problem| | {{Theorem|Set Cover Problem| | ||
*'''Input''': a number of sets <math>S_1,S_2,\ldots,S_n</math> with the universe <math>U=\bigcup_{i=1}^nS_i</math>; | *'''Input''': a number of sets <math>S_1,S_2,\ldots,S_n</math> with the universe <math>U=\bigcup_{i=1}^nS_i</math>; | ||
*'''Output''': the smallest <math>C\subseteq\{1,2,\ldots,n\}</math> such that <math>U=\bigcup_{i\in C}S_i</math>. | *'''Output''': the smallest <math>C\subseteq\{1,2,\ldots,n\}</math> such that <math>U=\bigcup_{i\in C}S_i</math>. | ||
}} | |||
We can think of each instance as a bipartite graph <math>G(U,\{S_1,S_2,\ldots,S_n\}, E)</math> with elements <math>x\in U</math> of the universe on the left side, subsets <math>S_1,S_2,\ldots,S_n</math> on the right side, and there is a bipartite edge between element <math>x</math> and set <math>S_i</math> if and only if <math>x\in S_i</math>. By this translation the set cover problem is precisely the problem of given as input a bipartite graph <math>G(U,V,E)</math>, to find the smallest subset <math>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>x\in U</math> is incident to some vertex in <math>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. | |||
{{Theorem|Hitting Set Problem| | |||
*'''Input''': a number of sets <math>S_1,S_2,\ldots,S_m</math> with the universe <math>U=\bigcup_{i=1}^mS_i</math>; | |||
*'''Output''': the smallest subset <math>C\subseteq U</math> of elements such that <math>C</math> intersects with every set <math>S_i</math> for <math>1\le i\le n</math>. | |||
}} | }} | ||
Revision as of 09:58, 25 September 2016
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 n }[/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].