Fast SDP Relaxations of Graph Cut Clustering, Transduction, and Other Combinatorial Problems
Abstract
The rise of convex programming has changed the face of many research fields in recent years, machine learning being one of the ones that benefitted the most. A very recent developement, the relaxation of combinatorial problems to semi-definite programs (SDP), has gained considerable attention over the last decade (Helmberg, 2000; De Bie and Cristianini, 2004a). Although SDP problems can be solved in polynomial time, for many relaxations the exponent in the polynomial complexity bounds is too high for scaling to large problem sizes. This has hampered their uptake as a powerful new tool in machine learning.
Cite
Text
De Bie and Cristianini. "Fast SDP Relaxations of Graph Cut Clustering, Transduction, and Other Combinatorial Problems." Journal of Machine Learning Research, 2006.Markdown
[De Bie and Cristianini. "Fast SDP Relaxations of Graph Cut Clustering, Transduction, and Other Combinatorial Problems." Journal of Machine Learning Research, 2006.](https://mlanthology.org/jmlr/2006/bie2006jmlr-fast/)BibTeX
@article{bie2006jmlr-fast,
title = {{Fast SDP Relaxations of Graph Cut Clustering, Transduction, and Other Combinatorial Problems}},
author = {De Bie, Tijl and Cristianini, Nello},
journal = {Journal of Machine Learning Research},
year = {2006},
pages = {1409-1436},
volume = {7},
url = {https://mlanthology.org/jmlr/2006/bie2006jmlr-fast/}
}