Communications in Mathematical Sciences
Volume 19 (2021)
Lovász extension and graph cut
Pages: 761 – 786
A set-pair Lovász extension is established to construct equivalent continuous optimization problems for graph $k$-cut problems.
Lovász extension, submodular, dual Cheeger cut, max cut, graph cut
2010 Mathematics Subject Classification
05C85, 58E05, 90C27, 90C35
This research was supported by the National Key R&D Program of China (No. 2020AAA0105200), the National Natural Science Foundation of China (Nos. 11822102, 11421101). S.S. is partially supported by Beijing Academy of Artificial Intelligence (BAAI). D.Z. is partially supported by the Project funded by China Postdoctoral Science Foundation (No. BX201700009).
Received 8 February 2020
Accepted 1 November 2020
Published 5 May 2021