高级算法 (Fall 2016)/Greedy and Local Search: Difference between revisions
Jump to navigation
Jump to search
imported>Etone |
imported>Etone No edit summary |
||
| Line 6: | Line 6: | ||
In other words, a set cover is a sub-collection of sets whose union "covers" all elements in the universe. | In other words, a set cover is a sub-collection of sets whose union "covers" all elements in the universe. | ||
{{Theorem|Set Cover| | {{Theorem|Set Cover Problem| | ||
*'''Input''': a number of sets <math>S_1,S_2,\ldots,S_n</math> defined on the universe <math>U=\bigcup_{i=1}^nS_i</math>; | *'''Input''': a number of sets <math>S_1,S_2,\ldots,S_n</math> defined on 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>. | ||
Revision as of 09:39, 25 September 2016
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].
In other words, a set cover 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] defined on 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].