Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Set_cover_problem> ?p ?o. }
Showing items 1 to 39 of
39
with 100 items per page.
- Set_cover_problem abstract "The set covering problem (SCP) is a classical question in combinatorics, computer science and complexity theory.It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms. It was also one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.Given a set of elements (called the universe) and a set of sets whose union equals the universe, the set cover problem is to identify the smallest subset of whose union equals the universe. For example, consider the universe and the set of sets . Clearly the union of is . However, we can cover all of the elements with the following, smaller number of sets: .More formally, given a universe and a family of subsets of ,a cover is a subfamily of sets whose union is . In the set covering decision problem, the input is a pair and an integer the question is whetherthere is a set covering of size or less. In the set covering optimization problem, the input is a pair , 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 .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.".
- Set_cover_problem wikiPageExternalLink book.pdf.
- Set_cover_problem wikiPageExternalLink node146.html.
- Set_cover_problem wikiPageExternalLink set-benchmarks.htm.
- Set_cover_problem wikiPageID "870399".
- Set_cover_problem wikiPageRevisionID "601950540".
- Set_cover_problem hasPhotoCollection Set_cover_problem.
- Set_cover_problem subject Category:NP-complete_problems.
- Set_cover_problem subject Category:Set_families.
- Set_cover_problem type Abstraction100002137.
- Set_cover_problem type Family108078020.
- Set_cover_problem type Group100031264.
- Set_cover_problem type Organization108008335.
- Set_cover_problem type SetFamilies.
- Set_cover_problem type SocialGroup107950920.
- Set_cover_problem type Unit108189659.
- Set_cover_problem type YagoLegalActor.
- Set_cover_problem type YagoLegalActorGeo.
- Set_cover_problem type YagoPermanentlyLocatedEntity.
- Set_cover_problem comment "The set covering problem (SCP) is a classical question in combinatorics, computer science and complexity theory.It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms.".
- Set_cover_problem label "Mengenüberdeckungsproblem".
- Set_cover_problem label "Problema del conjunto de cobertura".
- Set_cover_problem label "Problème de couverture par ensembles".
- Set_cover_problem label "Set cover problem".
- Set_cover_problem label "Verzamelingenoverdekking".
- Set_cover_problem label "Задача о покрытии множества".
- Set_cover_problem label "集合被覆問題".
- Set_cover_problem sameAs Mengenüberdeckungsproblem.
- Set_cover_problem sameAs Problema_del_conjunto_de_cobertura.
- Set_cover_problem sameAs Problème_de_couverture_par_ensembles.
- Set_cover_problem sameAs 集合被覆問題.
- Set_cover_problem sameAs 집합_덮개_문제.
- Set_cover_problem sameAs Verzamelingenoverdekking.
- Set_cover_problem sameAs m.03k6tg.
- Set_cover_problem sameAs Q1192100.
- Set_cover_problem sameAs Q1192100.
- Set_cover_problem sameAs Set_cover_problem.
- Set_cover_problem wasDerivedFrom Set_cover_problem?oldid=601950540.
- Set_cover_problem isPrimaryTopicOf Set_cover_problem.