On the optimality of the random hyperplane rounding technique for MAX CUT.
Uriel FeigeGideon SchechtmanPublished in: Random Struct. Algorithms (2002)
Keyphrases
- hyperplane
- max cut
- training samples
- feature space
- data points
- support vector
- input space
- graph model
- planar graphs
- np hard
- principal components
- graph partitioning
- convex hull
- approximation algorithms
- optimal solution
- support vector machine
- linear programming
- svm classifier
- np complete problems
- kernel function
- low dimensional
- data mining
- lower bound
- feature extraction