高级算法 (Fall 2016)/Greedy and Local Search: Difference between revisions
Jump to navigation
Jump to search
imported>Etone No edit summary |
imported>Etone |
||
| Line 2: | Line 2: | ||
= Set cover = | = Set cover = | ||
Given a family of sets <math>\mathcal{F}=\{S_1,S_2,\ldots,S_n\}\subseteq 2^{U}</math> where every member <math>S_i\in\mathcal{F}</math> in the family is a subset of a universe <math>U</math>, a '''set cover''' is a sub-collection <math>\mathcal{C}\subseteq\mathcal{F}</math> such that | |||
:<math>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. | |||
{{Theorem|Set Cover| | |||
*'''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>. | |||
}} | |||
= Scheduling = | = Scheduling = | ||
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 - 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].