Submodular function minimization and polarity
Submodular function minimization and polarity
复制标题
子模函数最小化和极性
DOI：
--
复制
发表时间：
2019
影响因子：
2.7
通讯作者：
Vishnu Narayanan
中科院分区：
文献类型：
--
作者：
Alper Atamtürk;Vishnu Narayanan
利用极性，给出了集合函数铭文的一个外多面体逼近。对于一个次模函数，我们证明了相应的极弛豫是精确的；因此，它相当于Lovász扩展。极坐标方法为子模函数题词的凸包描述提供了另一种证明。计算实验表明，从外部逼近得到的不等式可以有效地作为求解次模和非次模集函数最小化问题的切割平面。
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 Lovász 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.
影响因子：
1.8
作者：
Shaoning Han;A. Gómez;O. Prokopyev
通讯作者：
Shaoning Han;A. Gómez;O. Prokopyev