Submodular function minimization and polarity
成果类型：
Article
署名作者：
Atamturk, Alper; Narayanan, Vishnu
署名单位：
University of California System; University of California Berkeley; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Bombay
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-020-01607-w
发表日期：
2022
页码：
57-67
关键词：
摘要：
Using polarity, we give an outer polyhedral approximation for the epigraph of set functions. For a submodular function, we prove that the corresponding polar relaxation is exact; hence, it is equivalent to the Lovasz extension. The polar approach provides an alternative proof for the convex hull description of the epigraph of a submodular function. Computational experiments show that the inequalities from outer approximations can be effective as cutting planes for solving submodular as well as non-submodular set function minimization problems.