Goemans–Williamson algorithm
GPTKB entity
Statements (23)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
gptkb:algorithm
|
| gptkbp:appliesTo |
gptkb:NP-hard_problems
|
| gptkbp:approximation_ratio |
0.87856
|
| gptkbp:category |
graph algorithms
approximation algorithms |
| gptkbp:citation |
gptkb:Improved_Approximation_Algorithms_for_Maximum_Cut_and_Satisfiability_Problems
1995 |
| gptkbp:field |
combinatorial optimization
computer science theoretical computer science |
| https://www.w3.org/2000/01/rdf-schema#label |
Goemans–Williamson algorithm
|
| gptkbp:influenced |
approximation algorithms
semidefinite programming applications |
| gptkbp:introduced |
gptkb:Michel_Goemans
gptkb:David_P._Williamson |
| gptkbp:introducedIn |
1995
|
| gptkbp:notableFor |
improved approximation for MAX-CUT
|
| gptkbp:publishedIn |
gptkb:Journal_of_the_ACM
|
| gptkbp:solvedBy |
gptkb:MAX-CUT_problem
|
| gptkbp:uses |
semidefinite programming
randomized rounding |
| gptkbp:bfsParent |
gptkb:Michel_Goemans
|
| gptkbp:bfsLayer |
6
|