formulasearchengine - User contributions [en]

Main Page

2014-08-13T10:46:53Z

ChantalFitzGibb:

In the branch of [[mathematical logic]] called [[model theory]], an '''elementary class''' (or '''axiomatizable class''') is a [[class (set theory)|class]] consisting of all [[structure (mathematical logic)|structures]] satisfying a fixed [[first-order logic|first-order]] [[theory (mathematical logic)|theory]].

== Definition ==

A [[class (set theory)|class]] ''K'' of [[structure (mathematical logic)|structures]] of a [[signature (logic)|signature]] σ is called an '''elementary class''' if there is a [[first-order logic|first-order]] [[theory (mathematical logic)|theory]] ''T'' of signature σ, such that ''K'' consists of all models of ''T'', i.e., of all σ-structures that satisfy ''T''. If ''T'' can be chosen as a theory consisting of a single first-order sentence, then ''K'' is called a '''basic elementary class'''.

More generally, ''K'' is a [[pseudoelementary class|pseudo-elementary class]] if there is a first-order theory ''T'' of a signature that extends σ, such that ''K'' consists of all σ-structures that are [[reduct]]s to σ of models of ''T''. In other words, a class ''K'' of σ-structures is pseudo-elementary [[iff]] there is an elementary class ''K<nowiki>'</nowiki>'' such that ''K'' consists of precisely the reducts to σ of the structures in ''K<nowiki>'</nowiki>''.

For obvious reasons, elementary classes are also called '''axiomatizable in first-order logic''', and basic elementary classes are called '''finitely axiomatizable in first-order logic'''. These definitions extend to other logics in the obvious way, but since the first-order case is by far the most important, '''axiomatizable''' implicitly refers to this case when no other logic is specified.

== Conflicting and alternative terminology ==

While the above is nowadays standard terminology in [[model theory|"infinite" model theory]], the slightly different earlier definitions are still in use in [[finite model theory]], where an elementary class may be called a '''Δ-elementary class''', and the terms '''elementary class''' and '''first-order axiomatizable class''' are reserved for basic elementary classes (Ebbinghaus et al. 1994, Ebbinghaus and Flum 2005). Hodges calls elementary classes [[axiomatizable class]]es, and he refers to basic elementary classes as '''definable classes'''. He also uses the respective synonyms '''EC class''' and '''EC<math>_\Delta</math> class''' (Hodges, 1993).

There are good reasons for this diverging terminology. The [[signature (logic)|signature]]s that are considered in general model theory are often infinite, while a single [[first-order logic|first-order]] [[sentence (mathematical logic)|sentence]] contains only finitely many symbols. Therefore basic elementary classes are atypical in infinite model theory. Finite model theory, on the other hand, deals almost exclusively with finite signatures. It is easy to see that for every finite signature σ and for every class ''K'' of σ-structures closed under isomorphism there is an elementary class <math>K'</math> of σ-structures such that ''K'' and <math>K'</math> contain precisely the same finite structures. Hence elementary classes are not very interesting for finite model theorists.

== Easy relations between the notions ==

Clearly every basic elementary class is an elementary class, and every elementary class is a pseudo-elementary class. Moreover, as an easy consequence of the [[compactness theorem]], a class of σ-structures is basic elementary if and only if it is elementary and its complement is also elementary.

== Examples ==
=== A basic elementary class ===
Let σ be a signature consisting only of a [[unary function]] symbol ''f''. The class ''K'' of σ-structures in which ''f'' is [[injection (mathematics)|one-to-one]] is a basic elementary class. This is witnessed by the theory ''T'', which consists only of the single sentence
:<math>\forall x\forall y( (f(x)=f(y)) \to (x=y) )</math>.

=== An elementary, basic pseudoelementary class that is not basic elementary ===
Let σ be an arbitrary signature. The class ''K'' of all infinite σ-structures is elementary. To see this, consider the sentences

:<math>\rho_2={}</math> "<math>\exist x_1\exist x_2(x_1 \not =x_2)</math>",

:<math>\rho_3={}</math> "<math>\exist x_1\exist x_2\exist x_3((x_1 \not =x_2) \and (x_1 \not =x_3) \and (x_2 \not =x_3))</math>",

and so on. (So the sentence <math>\rho_n</math> says that there are at least ''n'' elements.) The infinite σ-structures are precisely the models of the theory

:<math>T_\infty=\{\rho_2, \rho_3, \rho_4, \dots\}</math>.

But ''K'' is not a basic elementary class. Otherwise the infinite σ-structures would be precisely those that satisfy a certain first-order sentence τ. But then the set
<math>\{\neg\tau, \rho_2, \rho_3, \rho_4, \dots\}</math> would be inconsistent. By the [[compactness theorem]], for some natural number ''n'' the set <math>\{\neg\tau, \rho_2, \rho_3, \rho_4, \dots, \rho_n\}</math> would be inconsistent. But this is absurd, because this theory is satisfied by any σ-structure with <math>n+1</math> or more elements.

However, there is a basic elementary class ''K<nowiki>'</nowiki>'' in the signature σ' = σ <math>\cup</math> {''f''}, where ''f'' is a unary function symbol, such that ''K'' consists exactly of the reducts to σ of σ'-structures in ''K<nowiki>'</nowiki>''. ''K<nowiki>'</nowiki>'' is axiomatised by the single sentence <math>(\forall x\forall y(f(x) = f(y) \rightarrow x=y) \land \exists y\neg\exists x(y = f(x))),</math>, which expresses that ''f'' is injective but not surjective. Therefore ''K'' is elementary and what could be called basic pseudo-elementary, but not basic elementary.

=== Pseudo-elementary class that is non-elementary ===
Finally, consider the signature σ consisting of a single unary relation symbol ''P''. Every σ-structure is [[partition of a set|partitioned]] into two subsets: Those elements for which ''P'' holds, and the rest. Let ''K'' be the class of all σ-structures for which these two subsets have the same [[cardinality]], i.e., there is a bijection between them. This class is not elementary, because a σ-structure in which both the set of realisations of ''P'' and its complement are countably infinite satisfies precisely the same first-order sentences as a σ-structure in which one of the sets is countably infinite and the other is uncountable.

Now consider the signature <math>\sigma'</math>, which consists of ''P'' along with a unary function symbol ''f''. Let <math>K'</math> be the class of all <math>\sigma'</math>-structures such that ''f'' is a bijection and ''P'' holds for ''x'' [[iff]] ''P'' does not hold for ''f(x)''. <math>K'</math> is clearly an elementary class, and therefore ''K'' is an example of a pseudo-elementary class that is not elementary.

=== Non-pseudo-elementary class===
Let σ be an arbitrary signature. The class ''K'' of all finite σ-structures is not elementary, because (as shown above) its complement is elementary but not basic elementary. Since this is also true for every signature extending σ, ''K'' is not even a pseudo-elementary class.

This example demonstrates the limits of expressive power inherent in [[first-order logic]] as opposed to the far more expressive [[second-order logic]]. Second-order logic, however, fails to retain many desirable properties of first-order logic, such as the compactness theorem.

== References ==

* {{Citation | last1=Chang | first1=Chen Chung | last2=Keisler | first2=H. Jerome | author2-link=Howard Jerome Keisler | title=Model Theory | origyear=1973 | publisher=[[Elsevier]] | edition=3rd | series=Studies in Logic and the Foundations of Mathematics | isbn=978-0-444-88054-3 | year=1990}}
* {{Citation | last1=Ebbinghaus | first1=Heinz-Dieter | last2=Flum | first2=Jörg | title=Finite model theory | origyear=1995 | publisher=[[Springer-Verlag]] | location=Berlin, New York | isbn=978-3-540-28787-2 | year=2005 | pages=360}}
* {{Citation | last1=Ebbinghaus | first1=Heinz-Dieter | last2=Flum | first2=Jörg | last3=Thomas | first3=Wolfgang | title=Mathematical Logic | publisher=[[Springer-Verlag]] | location=Berlin, New York | edition=2nd | isbn=978-0-387-94258-2 | year=1994}}
* {{Citation | last1=Hodges | first1=Wilfrid | author1-link=Wilfrid Hodges | title=A shorter model theory | publisher=[[Cambridge University Press]] | isbn=978-0-521-58713-6 | year=1997}}
* {{Citation | last1=Poizat | first1=Bruno | title=A Course in Model Theory: An Introduction to Contemporary Mathematical Logic | publisher=[[Springer-Verlag]] | location=Berlin, New York | isbn=978-0-387-98655-5 | year=2000}}

{{DEFAULTSORT:Elementary Class}}
[[Category:Model theory]]

[[de:Elementare Klasse]]
[[nl:Elementaire klasse]]

Main Page

2014-08-13T10:45:47Z

ChantalFitzGibb:

In [[mathematics]], the term '''''hyperbolic triangle''''' has more than one meaning.

[[Image:Uniform tiling 73-t2.png|thumb|right|200px|A tiling of the hyperbolic plane with hyperbolic triangles – the [[order-7 triangular tiling]].]]

==Hyperbolic geometry==
In [[hyperbolic geometry]], a '''hyperbolic triangle''' is a figure in the hyperbolic plane, analogous to a triangle in Euclidean geometry, consisting of three sides and three angles. The relations among the angles and sides are analogous to those of [[spherical trigonometry]]; they are most conveniently stated if the lengths are measured in terms of a special unit of length analogous to a [[radian]]. In terms of the [[Gaussian curvature]] ''K'' of the plane this unit is given by

::<math>R=\frac{1}{\sqrt{-K}}.</math>

In all the trig formulas stated below the sides ''a'', ''b'', and ''c'' must be measured in this unit. In a hyperbolic triangle the sum of the angles ''A'', ''B'', ''C'' (respectively opposite to the side with the corresponding letter) is strictly less than a [[straight angle]]. The difference is often called the [[defect (geometry)|defect]] of the triangle. The area of a hyperbolic triangle is equal to its defect multiplied by the square of ''R'':

::<math>(\pi-A-B-C) R^2{}{}.\!</math>

The corresponding theorem in [[spherical geometry]] is [[Girard's theorem]] first proven by [[Johann Heinrich Lambert]].

===Right triangles===

If ''C'' is a right angle then:

*The '''sine''' of angle A is the ratio of the '''hyperbolic sine''' of the side opposite the angle to the '''hyperbolic sine''' of the [[hypotenuse]].
:: <math>\sin A=\frac{\textrm{sinh(opposite)}}{\textrm{sinh(hypotenuse)}}=\frac{\sinh a}{\,\sinh c\,}.\,</math>
*The '''cosine''' of angle A is the ratio of the '''hyperbolic tangent''' of the adjacent leg to the '''hyperbolic tangent''' of the hypotenuse.
:: <math>\cos A=\frac{\textrm{tanh(adjacent)}}{\textrm{tanh(hypotenuse)}}=\frac{\tanh b}{\,\tanh c\,}.\,</math>
*The '''tangent''' of angle A is the ratio of the '''hyperbolic tangent''' of the opposite leg to the '''hyperbolic sine''' of the adjacent leg.
:: <math>\tan A=\frac{\textrm{tanh(opposite)}}{\textrm{sinh(adjacent)}}=\frac{\tanh a}{\,\sinh b\,}.\,</math>

The hyperbolic sine, cosine, and tangent are [[hyperbolic functions]] which are analogous to the standard trigonometric functions.

===Oblique triangles===

Whether ''C'' is a right angle or not, the following relationships hold.

There is a [[hyperbolic law of cosines|law of cosines]]:

:: <math>\cosh c=\cosh a\cosh b-\sinh a\sinh b \cos C,\,</math>

its dual:

:: <math>\cos C= -\cos A\cos B+\sin A\sin B \cosh c,\,</math>

a law of sines:

:<math>\frac{\sin A}{\sinh a} = \frac{\sin B}{\sinh b} = \frac{\sin C}{\sinh c},</math>

and a four-parts formula:

:: <math>\cos C\cosh a=\sinh a\coth b-\sin C\cot B.\,</math>

===Ideal triangles===

If a pair of sides is asymptotic they may be said to form an angle of zero. In [[projective geometry]], they meet at an '''ideal vertex''' on the circle at infinity. If all three are vertices are ideal, then the resulting figure is called an '''[[ideal triangle]]'''. An ideal hyperbolic triangle has an angle sum of 0°, a property it has in common with the triangular area in the Euclidean plane bounded by three tangent circles.

==Euclidean geometry==
[[Image:Hyperbolic sector.svg|200px|right]]
In the foundations of the [[hyperbolic function]]s sinh, cosh and tanh, a '''hyperbolic triangle''' is a [[right triangle]] in the [[first quadrant of the Cartesian plane]]
:<math>\{(x,y):x,y \in \mathbb R\},</math>
with one [[vertex (geometry)|vertex]] at the origin, base on the diagonal ray ''y'' = ''x'', and third vertex on the [[hyperbola]]

:<math>xy=1.\,</math>

The length of the base of such a triangle is
:<math>\sqrt 2 \cosh u,\,</math>
and the [[altitude (triangle)|altitude]] is
:<math>\sqrt 2 \sinh u,\,</math>
where ''u'' is the appropriate [[hyperbolic angle]].

==See also==
* [[Hyperbolic law of cosines]]
* [[Pair of pants]]
* [[Triangle group]]

==References==
{{inline|date=November 2011}}
* [[Augustus De Morgan]] (1849) [http://books.google.com/books?id=7UwEAAAAQAAJ Trigonometry and Double Algebra], Chapter VI: "On the connection of common and hyperbolic trigonometry".
*{{citation|first=Wilson|last=Stothers|title=Hyperbolic geometry|url=http://www.maths.gla.ac.uk/~wws/cabripages/hyperbolic/hyperbolic0.html|publisher=[[University of Glasgow]]|year=2000}}, interactive instructional website.
* Svetlana Katok, ''Fuchsian Groups'' (1992), University of Chicago Press, Chicago ISBN 0-226-42583-5 ''(Provides a brief but simple, easily readable review in chapter 1.)''

{{DEFAULTSORT:Hyperbolic Triangle}}
[[Category:Hyperbolic geometry]]

[[it:Triangolo iperbolico]]
[[pl:Trójkąt asymptotyczny]]
[[pt:Triângulo hiperbólico]]
[[sv:Hyperbolisk triangel]]

Main Page

2014-08-12T21:09:12Z

ChantalFitzGibb:

The '''set covering problem''' ('''SCP''') is a classical question in [[combinatorics]], [[computer science]] and [[Computational complexity theory|complexity theory]].

It is a problem "whose study has led to the development of fundamental techniques for the entire field" of [[approximation algorithms]].<ref>{{harvtxt|Vazirani|2001|p=15}}</ref> It was also one of [[Karp's 21 NP-complete problems]] shown to be [[NP-complete]] in 1972.

Given a set of elements <math>\{1,2,...,m\}</math> (called the universe) and a set <math>S</math> of <math>n</math> sets whose union equals the universe, the set cover problem is to identify the smallest subset of <math>S</math> whose union equals the universe. For example, consider the universe <math>U = \{1, 2, 3, 4, 5\}</math> and the set of sets <math>S = \{\{1, 2, 3\}, \{2, 4\}, \{3, 4\}, \{4, 5\}\}</math>. Clearly the union of <math>S</math> is <math>U</math>. However, we can cover all of the elements with the following, smaller number of sets: <math>\{\{1, 2, 3\}, \{4, 5\}\}</math>.

More formally, given a universe <math>\mathcal{U}</math> and a family <math>\mathcal{S}</math> of subsets of <math>\mathcal{U}</math>,
a ''cover'' is a subfamily <math>\mathcal{C}\subseteq\mathcal{S}</math> of sets whose union is <math>\mathcal{U}</math>. In the set covering [[decision problem]], the input is a pair <math>(\mathcal{U},\mathcal{S})</math> and an integer <math>k</math>; the question is whether
there is a set covering of size <math>k</math> or less. In the set covering [[optimization problem]], the input is a pair <math>(\mathcal{U},\mathcal{S})</math>, and the task is to find a set covering that uses the fewest sets.

The decision version of set covering is [[NP-complete]], and the optimization version of set cover is [[NP-hard]] .{{sfn |Korte|Vygen|2012|p=414}}

If additionally, you want to minimize the cost of the sets, it becomes Weighted Set Cover Problem. Otherwise, its an Un-weighted Set Cover Problem with all costs equal to one.

{{Covering-Packing Problem Pairs}}

==Integer linear program formulation==
The minimum set cover problem can be formulated as the following [[integer linear program]] (ILP).<ref>{{harvtxt|Vazirani|2001|p=108}}</ref>
{|
| minimize
| <math>\sum_{S \in \mathcal S} x_S</math>
|
| (minimize the number of sets)
|-
| subject to
| <math>\sum_{S\colon e \in S} x_S \geqslant 1 </math>
| for all <math>e\in \mathcal U</math>
| (cover every element of the universe)
|-
|
| <math>x_S \in \{0,1\}</math>
| for all <math>S\in \mathcal S</math>.
| (every set is either in the set cover or not)
|}
This ILP belongs to the more general class of ILPs for [[covering problem]]s.
The [[Linear programming relaxation#Approximation and integrality gap|integrality gap]] of this ILP is at most <math>\scriptstyle \log n</math>, so its [[Linear programming relaxation|relaxation]] gives a factor-<math>\scriptstyle \log n</math> [[approximation algorithm]] for the minimum set cover problem (where <math>\scriptstyle n</math> is the size of the universe).<ref>{{harvtxt|Vazirani|2001|pp=110–112}}</ref>

== Hitting set formulation ==
Set covering is equivalent to the '''hitting set problem'''. It is easy to see this by observing that an instance of set covering can
be viewed as an arbitrary [[bipartite graph]], with sets represented by vertices on the left, the universe represented by vertices on the
right, and edges representing the inclusion of elements in sets. The task is then to find a minimum cardinality subset of left-vertices which covers all of the right-vertices. In the Hitting set problem, the objective is to cover the left-vertices using a minimum subset of the right vertices. Converting from one problem to the other is therefore achieved by interchanging the two sets of vertices.

== Greedy algorithm ==

The [[greedy algorithm]] for set covering chooses sets according to one rule: at each stage, choose the set that contains the largest number of uncovered elements. It can be shown<ref>Chvatal, V. [http://www.jstor.org/stable/3689577 A Greedy Heuristic for the Set-Covering Problem]. Mathematics of Operations Research
Vol. 4, No. 3 (Aug., 1979), pp. 233-235</ref> that this algorithm achieves an approximation ratio of <math>H(s)</math>, where <math>s</math> is the size of the set to be covered, <math>H(n)</math> is the <math>n</math>-th [[harmonic number]]:

:<math> H(n) = \sum_{k=1}^{n} \frac{1}{k} \le \ln{n} +1</math>

This greedy algorithm actually achieves an approximation ratio of <math>H(s^\prime)</math> where <math>s^\prime</math> is the maximum cardinality set of <math>S</math>.

[[Image:SetCoverGreedy.gif|frame|Tight example for the greedy algorithm with k=3]]
There is a standard example on which the greedy algorithm achieves an approximation ratio of <math>\log_2(n)/2</math>.
The universe consists of <math>n=2^{(k+1)}-2</math> elements. The set system consists of <math>k</math> pairwise disjoint sets
<math>S_1,\ldots,S_k</math> with sizes <math>2,4,8,\ldots,2^k</math> respectively, as well as two additional disjoint sets <math>T_0,T_1</math>,
each of which contains half of the elements from each <math>S_i</math>. On this input, the greedy algorithm takes the sets
<math>S_k,\ldots,S_1</math>, in that order, while the optimal solution consists only of <math>T_0</math> and <math>T_1</math>.
An example of such an input for <math>k=3</math> is pictured on the right.

Inapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for set cover
(see [[Set cover problem#Inapproximability results|Inapproximability results]] below), under plausible complexity assumptions.

== Low-frequency systems ==

If each element occurs in at most ''f'' sets, then a solution can be found in polynomial time that approximates the optimum to within a factor of ''f'' using [[Linear programming relaxation|LP relaxation]].<ref>{{harvtxt|Vazirani|2001|pp=118–119}}</ref>

== Inapproximability results ==

When <math> n</math> refers to the size of the universe, {{harvtxt |Lund|Yannakakis|1994}} showed that set covering cannot be approximated in polynomial time to within a factor of <math>\tfrac{1}{2}\log_2{n} \approx 0.72\ln{n}</math>, unless '''NP''' has [[quasi-polynomial time]] algorithms. Feige (1998) improved this lower bound to <math>\bigl(1-o(1)\bigr)\cdot\ln{n}</math> under the same assumptions, which essentially matches the approximation ratio achieved by the greedy algorithm. {{harvtxt |Raz|Safra|1997}} established a lower bound
of <math>c\cdot\ln{n}</math>, where <math>c</math> is a constant, under the weaker assumption that '''P'''<math>\not=</math>'''NP'''.
A similar result with a higher value of <math>c</math> was recently proved by {{harvtxt |Alon|Moshkovitz|Safra|2006}}.

== Related problems ==
* Hitting set is an equivalent reformulation of Set Cover.
* [[Vertex cover problem|Vertex cover]] is a special case of Hitting Set.
* [[Edge cover problem|Edge cover]] is a special case of Set Cover.
* [[Set packing]] is the dual problem of Set Cover.
* [[Maximum coverage problem]] is to choose at most k sets to cover as many elements as possible.
* [[Dominating set]] is the problem of selecting a set of vertices (the dominating set) in a graph such that all other vertices are adjacent to at least one vertex in the dominating set. The Dominating set problem was shown to be NP complete through a reduction from Set cover.
* [[Exact cover problem]] is to choose a set cover with no element included in more than one covering set.
* [[Closest pair of points problem]]
* [[Nearest neighbor search]]

==See also==
*[[MinHash]]
*[[Sequence assembly]]

==Notes==

{{reflist}}

== References ==

* {{Citation | last1=Alon | first1=Noga | author1-link=Noga Alon | last2=Moshkovitz | first2=Dana | last3=Safra | first3=Shmuel | author3-link=Shmuel Safra | title=Algorithmic construction of sets for k-restrictions | publisher=ACM | year=2006 | journal=ACM Trans. Algorithms | issn=1549-6325 | volume=2 | issue=2 | pages=153–177 | doi=10.1145/1150334.1150336}}.
* {{Citation
| last=Cormen | first=Thomas H. | authorlink=Thomas H. Cormen
| last2=Leiserson | first2=Charles E. | authorlink2=Charles E. Leiserson
| last3=Rivest | first3=Ronald L. | authorlink3=Ronald L. Rivest
| last4=Stein | first4=Clifford | authorlink4=Clifford Stein
| title=Introduction to Algorithms | year=2001 | publisher=MIT Press and McGraw-Hill | location=Cambridge, Mass.
| isbn=0-262-03293-7 | pages=1033–1038}}
* {{Citation | last1=Feige | first1=Uriel | author1-link=Uriel Feige | title=A threshold of ln n for approximating set cover | publisher=ACM | year=1998 | journal=[[Journal of the ACM]] | issn=0004-5411 | volume=45 | issue=4 | pages=634–652 | doi=10.1145/285055.285059}}.
* {{Citation | last1=Lund | first1=Carsten | author1-link=Carsten Lund | last2=Yannakakis | first2=Mihalis | author2-link=Mihalis Yannakakis | title=On the hardness of approximating minimization problems | publisher=ACM | year=1994 | journal=[[Journal of the ACM]] | issn=0004-5411 | volume=41 | issue=5 | pages=960–981 | doi=10.1145/185675.306789}}.
* {{Citation | last1=Raz | first1=Ran | author1-link=Ran Raz | last2=Safra | first2=Shmuel | author2-link=Shmuel Safra | title=STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing | publisher=ACM | isbn=978-0-89791-888-6 | year=1997 | chapter=A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP | pages=475–484}}.
* {{cite book
| last = Vazirani | first = Vijay V.
| authorlink = Vijay Vazirani
| title = Approximation Algorithms
| year = 2001
| publisher = Springer-Verlag
| isbn = 3-540-65367-8
| url = http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pdf
| ref = harv
}}
* {{cite book
| last1 = Korte | first1 = Bernhard
| last2 = Vygen | first2 = Jens
| title = Combinatorial Optimization: Theory and Algorithms
| year = 2012
| isbn = 978-3-642-24487-2
| edition = 5
| publisher = Springer
| ref = harv
}}

== External links ==
* [http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/set-benchmarks.htm Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination]
* [http://www.csc.kth.se/~viggo/wwwcompendium/node146.html A compendium of NP optimization problems - Minimum Set Cover]

{{DEFAULTSORT:Set Cover Problem}}
[[Category:Set families]]
[[Category:NP-complete problems]]