Communications in Mathematical Sciences

Volume 19 (2021)

Number 3

Lovász extension and graph cut

Pages: 761 – 786

DOI: https://dx.doi.org/10.4310/CMS.2021.v19.n3.a9

Authors

Kung-Ching Chang (Laboratory of Mathematics and Its Applications (LMAM) and School of Mathematical Sciences, Peking University, Beijing, China)

Sihong Shao (LMAM and School of Mathematical Sciences, Peking University, Beijing, China)

Dong Zhang (LMAM and School of Mathematical Sciences, Peking University, Beijing, China)

Weixi Zhang (LMAM and School of Mathematical Sciences, Peking University, Beijing, China)

Abstract

A set-pair Lovász extension is established to construct equivalent continuous optimization problems for graph $k$-cut problems.

Keywords

Lovász extension, submodular, dual Cheeger cut, max cut, graph cut

2010 Mathematics Subject Classification

05C85, 58E05, 90C27, 90C35

Full Text (PDF format)

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