|
gptkbp:instanceOf
|
gptkb:theoretical_computer_science
gptkb:NP-complete_problem
|
|
gptkbp:appearsIn
|
gptkb:Karp's_21_NP-complete_problems
|
|
gptkbp:cannot_be_approximated_within
|
(1-o(1))ln(n) unless P=NP
|
|
gptkbp:category
|
covering problem
|
|
gptkbp:complexity
|
NP-complete
|
|
gptkbp:decision_problem
|
yes
|
|
gptkbp:definedIn
|
Given a universe U and a collection S of subsets of U, find the smallest sub-collection of S whose union equals U
|
|
gptkbp:field
|
gptkb:combinatorics
gptkb:theoretical_computer_science
computer science
|
|
gptkbp:first_proven_NP-complete_by
|
gptkb:Richard_Karp
|
|
gptkbp:greedy_algorithm_approximation_ratio
|
ln(n)
|
|
gptkbp:has_approximation_algorithm
|
greedy algorithm
|
|
gptkbp:has_unweighted_version
|
gptkb:unweighted_set_cover_problem
|
|
gptkbp:has_weighted_version
|
weighted set cover problem
|
|
gptkbp:hasSpecialCase
|
integer programming
|
|
gptkbp:input
|
collection of subsets
universe of elements
|
|
gptkbp:optimization_problem
|
yes
|
|
gptkbp:output
|
minimum number of subsets covering the universe
|
|
gptkbp:relatedTo
|
gptkb:vertex_cover_problem
gptkb:set_packing_problem
hitting set problem
|
|
gptkbp:solved_approximately_by
|
greedy algorithm
|
|
gptkbp:solved_exactly_by
|
gptkb:integer_linear_programming
brute-force search
|
|
gptkbp:used_in
|
gptkb:machine_learning
resource allocation
data mining
scheduling
network design
|
|
gptkbp:year_of_NP-completeness_proof
|
1972
|
|
gptkbp:bfsParent
|
gptkb:NP_languages
gptkb:Hitting_Set
|
|
gptkbp:bfsLayer
|
7
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
Set cover problem
|