|
gptkbp:instanceOf
|
gptkb:theoretical_computer_science
gptkb:graph
|
|
gptkbp:approximationRatio
|
0.878
|
|
gptkbp:complexity
|
NP-complete
|
|
gptkbp:definedIn
|
gptkb:graph
|
|
gptkbp:estimatedCost
|
gptkb:Goemans–Williamson_algorithm
|
|
gptkbp:field
|
gptkb:theoretical_computer_science
combinatorial optimization
|
|
gptkbp:goal
|
partition vertices into two sets to maximize number of edges between sets
|
|
gptkbp:hasApplication
|
gptkb:machine_learning
gptkb:statistical_mechanics
network design
|
|
gptkbp:hasExactAlgorithm
|
exponential time algorithm
|
|
gptkbp:hasSemidefiniteProgrammingRelaxation
|
gptkb:Goemans–Williamson_algorithm
|
|
gptkbp:hasSpecialCase
|
gptkb:Ising_model
gptkb:quadratic_unconstrained_binary_optimization
|
|
gptkbp:introduced
|
gptkb:E._L._Lawler
|
|
gptkbp:introducedIn
|
1976
|
|
gptkbp:isHardFor
|
planar graphs
|
|
gptkbp:isNPCompleteFor
|
general graphs
|
|
gptkbp:isPolynomialTimeSolvableFor
|
planar graphs
bipartite graphs
graphs with no K5 minor
|
|
gptkbp:relatedTo
|
minimum cut
graph partitioning
|
|
gptkbp:usedIn
|
statistical physics
VLSI design
community detection
circuit layout
|
|
gptkbp:bfsParent
|
gptkb:Karp's_21_NP-complete_problems
|
|
gptkbp:bfsLayer
|
6
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
Max Cut
|