set cover problem (optimization version)
GPTKB entity
Statements (31)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
theoretical computer science
mathematical optimization |
| gptkbp:application |
resource allocation
data mining scheduling network design |
| gptkbp:approximation |
logarithmic approximation ratio
|
| gptkbp:approximationAlgorithm |
greedy algorithm
|
| gptkbp:category |
combinatorial problem
covering problem |
| gptkbp:complexity |
gptkb:NP-hard
|
| gptkbp:defines |
Given a universe U and a collection S of subsets of U, find the smallest subcollection of S whose union is U.
|
| gptkbp:field |
combinatorial optimization
computer science theoretical computer science |
| gptkbp:formedBy |
Karp, 1972
|
| gptkbp:greedyAlgorithmPerformance |
ln(n) approximation
|
| gptkbp:hardnessOfApproximation |
cannot be approximated within (1-o(1))ln n unless P=NP
|
| https://www.w3.org/2000/01/rdf-schema#label |
set cover problem (optimization version)
|
| gptkbp:input |
collection S of subsets of U
universe U |
| gptkbp:NP-hardness |
gptkb:NP-hard
|
| gptkbp:output |
smallest subcollection of S covering U
|
| gptkbp:reduces |
vertex cover
hitting set |
| gptkbp:relatedTo |
gptkb:vertex_cover_problem
gptkb:set_packing_problem hitting set problem set cover problem (decision version) |
| gptkbp:bfsParent |
gptkb:NP-hard_problems
|
| gptkbp:bfsLayer |
7
|