About: Set cover problem

Property	Value
dbo:description	בעיה קלאסית בקומבינטוריקה, מדעי המחשב, אופטימיזציה וסיבוכיות הבעיה נכללת ברשימת 21 הבעיות ה-NP-שלמות של קארפ (iw) Mathematisches Problem aus dem Gebiet der Kombinatorik (de) classical problem in combinatorics (en) класичне питання інформатики і теорії складності (uk)
dbo:thumbnail	wiki-commons:Special:FilePath/SetCover.svg?width=300
dbo:wikiPageExternalLink	http://www.csc.kth.se/~viggo/wwwcompendium/node146.html http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/set-benchmarks.htm http://dx-2014.ist.tugraz.at/papers/DX14_Mon_PM_S1_paper1.pdf https://books.google.com/books%3Fid=IMmuF0RZk1MC&q=karpinski+zelikovsky+cover+dense&pg=PA169 https://www.ics.uci.edu/~vazirani/book.pdf
dbo:wikiPageWikiLink	dbr:Edge_cover_problem dbr:Combinatorics dbr:Computer_science dbr:Bucket_queue dbr:Computational_complexity_theory dbr:Universe_(mathematics) dbr:Decision_problem dbr:Set_packing dbr:Harmonic_number dbr:Greedy_algorithm dbr:Set_(mathematics) dbr:Bipartite_graph dbr:Union_(set_theory) dbr:Weighting dbr:Optimization_problem dbr:Approximation_algorithm dbr:Karp's_21_NP-complete_problems dbr:Uriel_Feige dbr:Dominating_set dbr:Set_cover_problem dbr:Operations_research dbr:Linear_programming_relaxation dbr:Journal_of_the_ACM dbc:Approximation_algorithms dbr:Maximum_coverage_problem dbc:Linear_programming dbc:NP-complete_problems dbc:Families_of_sets dbc:Covering_problems dbr:Randomized_rounding dbr:Approximation_algorithms dbr:NP-complete dbr:Quasi-polynomial_time dbr:NP-hard dbr:Exact_cover_problem dbr:Covering_problem dbr:Geometric_Set_Cover_Problem dbr:Integer_linear_program dbr:Set-cover_abduction dbr:Vertex_cover_problem dbr:File:SetCoverGreedy.gif
dbp:wikiPageUsesTemplate	dbt:Anchor dbt:Citation dbt:Expand_section dbt:Harvtxt dbt:Math dbt:Mvar dbt:Reflist dbt:Sfn dbt:Short_description dbt:Var dbt:Commons_category dbt:Covering-Packing_Problem_Pairs
dct:subject	dbc:Approximation_algorithms dbc:Linear_programming dbc:NP-complete_problems dbc:Families_of_sets dbc:Covering_problems
rdfs:label	Set cover problem (en) Mengenüberdeckungsproblem (de) Problema del conjunto de cobertura (es) Problème de couverture par ensembles (fr) 集合被覆問題 (ja) 집합 덮개 문제 (ko) Problema de cobertura de conjuntos (pt) Verzamelingenoverdekking (nl) Задача про покриття множини (uk) Задача о покрытии множества (ru) 集合覆盖问题 (zh)
owl:sameAs	freebase:Set cover problem yago-res:Set cover problem wikidata:Set cover problem dbpedia-de:Set cover problem dbpedia-es:Set cover problem dbpedia-nl:Set cover problem dbpedia-fr:Set cover problem dbpedia-he:Set cover problem dbpedia-ja:Set cover problem dbpedia-pt:Set cover problem dbpedia-ru:Set cover problem dbpedia-zh:Set cover problem dbpedia-ko:Set cover problem dbpedia-fa:Set cover problem dbpedia-th:Set cover problem dbpedia-uk:Set cover problem dbpedia-global:Set cover problem
prov:wasDerivedFrom	wikipedia-en:Set_cover_problem?oldid=1294915153&ns=0
foaf:depiction	wiki-commons:Special:FilePath/SetCover.svg wiki-commons:Special:FilePath/SetCoverGreedy.gif
foaf:isPrimaryTopicOf	wikipedia-en:Set_cover_problem
is dbo:wikiPageDisambiguates of	dbr:SCP
is dbo:wikiPageRedirects of	dbr:Hitting_set_problem dbr:Hitting_set dbr:Set-covering_problem dbr:Set_Cover dbr:Set_cover dbr:Set_covering dbr:Set_covering_problem
is dbo:wikiPageWikiLink of	dbr:The_Art_of_Computer_Programming dbr:Covering_problems dbr:Combinatorial_optimization dbr:Vertex_cover_in_hypergraphs dbr:Memetic_algorithm dbr:Bucket_queue dbr:Automatic_summarization dbr:Graph_theory dbr:Set_packing dbr:Greedy_algorithm dbr:Cover_(topology) dbr:Polygon_covering dbr:Bounded_expansion dbr:Geometric_set_cover_problem dbr:Sequence_assembly dbr:Ant_colony_optimization_algorithms dbr:Steiner_tree_problem dbr:Matching_in_hypergraphs dbr:Linear_programming dbr:Approximation_algorithm dbr:Karp's_21_NP-complete_problems dbr:Quine–McCluskey_algorithm dbr:Shmuel_Safra dbr:Branch_and_bound dbr:Sunflower_(mathematics) dbr:Dominating_set dbr:Ε-net_(computational_geometry) dbr:Set_cover_problem dbr:PLS_(complexity) dbr:Packing_in_a_hypergraph dbr:Aztec_diamond dbr:Blake_canonical_form dbr:SCP dbr:Linear_programming_relaxation dbr:Discrete_Mathematics_(journal) dbr:Václav_Chvátal dbr:List_of_computability_and_complexity_topics dbr:List_of_NP-complete_problems dbr:Maximum_coverage_problem dbr:Multiplicative_weight_update_method dbr:Facility_location_problem dbr:Peptide_computing dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Metric_dimension_(graph_theory) dbr:Index_of_combinatorics_articles dbr:Toponym_resolution dbr:K-approximation_of_k-hitting_set dbr:Numbers_(season_4) dbr:Shortest_common_supersequence_problem dbr:Hitting_set_problem dbr:Hitting_set dbr:Set-covering_problem dbr:Set_Cover dbr:Set_cover dbr:Set_covering dbr:Set_covering_problem
is foaf:primaryTopic of	wikipedia-en:Set_cover_problem