高级算法 (Fall 2016)/Greedy and Local Search: Difference between revisions
imported>Etone |
imported>Etone No edit summary |
||
| 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 | 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. | In other words, a set cover is a sub-collection of sets whose union "covers" all elements in the universe. | ||
| Line 10: | Line 9: | ||
*'''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>. | ||
}} | }} | ||
Given an undirected graph <math>G(U,V)</math>, a '''vertex cover''' is a subset <math>C\subseteq V</math> of vertices such that every edge <math>uv\in E</math> has at least one endpoint in <math>C</math>. | |||
= Scheduling = | = Scheduling = | ||
Revision as of 09:42, 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] 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].