Lovász extension and graph cut (Q2057034)

The Lovász extension provides a way to find an equivalent continuous optimization problem formulation for discrete and combinatorial problems. The authors extend this concept and apply it to the graph \(k\)-cut (in particular dual Cheeger cut) problem. They give an equivalent continuous formulation of the 3-cut problem and provide an approach to the general \(k\)-cut problem.