Solution Stability in Linear Programming Relaxations: Graph Partitioning and Unsupervised Learning

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 correlat