Statements (35)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
Combinatorial Optimization Problem
|
| gptkbp:application |
gptkb:Crew_Scheduling
gptkb:Facility_Location Resource Allocation Network Design |
| gptkbp:approximationAlgorithm |
gptkb:Greedy_Algorithm
|
| gptkbp:approximationRatio |
ln(n)
|
| gptkbp:complexity |
gptkb:NP-hard
|
| gptkbp:decision |
Does there exist a cover of size k or less?
|
| gptkbp:defines |
Given a universe of elements and a collection of subsets, the goal is to find the smallest sub-collection of subsets whose union covers the entire universe.
|
| gptkbp:field |
gptkb:Mathematics
Computer Science Operations Research |
| gptkbp:firstFormulatedIn |
1972
|
| gptkbp:form |
gptkb:Integer_Linear_Programming
|
| gptkbp:formedBy |
gptkb:Richard_M._Karp
|
| https://www.w3.org/2000/01/rdf-schema#label |
Set Covering Problem
|
| gptkbp:input |
Collection of subsets
Universe of elements |
| gptkbp:NP-complete |
Yes
|
| gptkbp:optimizedFor |
Minimization
|
| gptkbp:output |
Smallest sub-collection of subsets covering the universe
|
| gptkbp:relatedStandard |
Karp, R. M. (1972). Reducibility among combinatorial problems.
|
| gptkbp:relatedTo |
Hitting Set Problem
Set Packing Problem Set Partitioning Problem Vertex Cover Problem |
| gptkbp:solvedBy |
gptkb:Branch_and_Bound
gptkb:Metaheuristics Heuristics Cutting Plane Methods |
| gptkbp:usedIn |
Algorithm Design Courses
Operations Research Textbooks |
| gptkbp:bfsParent |
gptkb:Integer_Programming
|
| gptkbp:bfsLayer |
6
|