Lovász extension and graph cut

DOI10.4310/CMS.2021.V19.N3.A9MaRDI QIDQ2057034zbMATH OpenFDO

Authors Sihong Shao, Dong Zhang, Weixi Zhang, Kung Ching Chang

Publication date 8 December 2021

Published in Communications in Mathematical Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.05257

zbMATH Keywords

Cheeger cutgraph cutLovász extensionmax cutsubmodular function

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Abstract critical point theory (Morse theory, Lyusternik-Shnirel'man theory, etc.) in infinite-dimensional spaces (58E05) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Abstract: A set-pair Lov'asz extension is established to construct equivalent continuous optimization problems for graph $k$-cut problems.

Review text

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.

Recommendations

• Graph cuts with interacting edge weights: examples, approximations, and algorithms
• Discrete convexity and polynomial solvability in minimum 0-extension problems
• On the \(k\)-cut problem
• Extended formulations for the \(A\)-cut problem
• Graph Partitioning and Continuous Quadratic Programming

Cited in

(1)

• Dual Cheeger constants, signless 1-Laplacians and maxcut

This page was built for publication: Lovász extension and graph cut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2057034)