Statements (29)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
mathematical optimization
|
| gptkbp:application |
clustering
statistical physics network design circuit layout design |
| gptkbp:approximationAlgorithm |
gptkb:Goemans–Williamson_algorithm
|
| gptkbp:approximationRatio |
0.878 (Goemans–Williamson algorithm)
|
| gptkbp:complexity |
gptkb:NP-hard
|
| gptkbp:defines |
Given a graph, the Max-Cut problem asks for a partition of the vertices into two sets such that the number (or weight) of edges between the sets is maximized.
|
| gptkbp:field |
theoretical computer science
graph theory |
| gptkbp:hasExactAlgorithm |
exponential time algorithms
|
| gptkbp:hasHeuristic |
gptkb:simulated_annealing
gptkb:genetic_algorithms local search |
| gptkbp:hasSpecialCase |
gptkb:quadratic_unconstrained_binary_optimization_(QUBO)
|
| https://www.w3.org/2000/01/rdf-schema#label |
Max-Cut problem
|
| gptkbp:input |
graph
|
| gptkbp:output |
maximum cut value
partition of vertices into two sets |
| gptkbp:relatedTo |
gptkb:Ising_model
semidefinite programming minimum cut problem |
| gptkbp:solvableInPolynomialTime |
no (for general graphs)
yes (for planar graphs) |
| gptkbp:studiedBy |
1970s
|
| gptkbp:usedIn |
quantum computing research
|
| gptkbp:bfsParent |
gptkb:Quantum_Approximate_Optimization_Algorithm
|
| gptkbp:bfsLayer |
6
|