@inproceedings{5878,
  title = {Solution Stability in Linear Programming Relaxations: Graph Partitioning and Unsupervised Learning},
  journal = {Proceedings of the 26th International Conference on Machine Learning (ICML 2009)},
  booktitle = {ICML 2009},
  abstract = {We propose a new method to quantify the solution
  stability of a large class of combinatorial
  optimization problems arising in machine
  learning. As practical example we apply the
  method to correlation clustering, clustering
  aggregation, modularity clustering, and relative
  performance significance clustering. Our
  method is extensively motivated by the idea
  of linear programming relaxations. We prove
  that when a relaxation is used to solve the
  original clustering problem, then the solution
  stability calculated by our method is conservative,
  that is, it never overestimates the solution
  stability of the true, unrelaxed problem.
  We also demonstrate how our method
  can be used to compute the entire path of
  optimal solutions as the optimization problem
  is increasingly perturbed. Experimentally,
  our method is shown to perform well
  on a number of benchmark problems.},
  pages = {769-776},
  editors = {Danyluk, A. , L. Bottou, M. Littman},
  publisher = {ACM Press},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {New York, NY, USA},
  month = jun,
  year = {2009},
  slug = {5878},
  author = {Nowozin, S. and Jegelka, S.},
  month_numeric = {6}
}