高级算法 (Fall 2016)/Greedy and Local Search: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
No edit summary
imported>Etone
Line 7: Line 7:


{{Theorem|Set Cover Problem|
{{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> 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>.
}}
}}


= Scheduling =
= Scheduling =

Revision as of 09:40, 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].

Scheduling