Minimizing submodular functions on diamonds via generalized fractional matroid matchings
Minimizing submodular functions on diamonds via generalized fractional matroid matchings
复制标题
通过广义分数拟阵匹配最小化钻石的子模函数
DOI：
10.1016/j.jctb.2022.07.005
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Tanigawa Shin-ichi
中科院分区：
文献类型：
--
作者：
Fujishige Satoru;Kiraly Tamas;Makino Kazuhisa;Takazawa Kenjiro;Tanigawa Shin-ichi
在本文中，我们展示了第一个多项式时间算法的问题，最小化次模函数的产品钻石有限大小。基于椭球方法，将子模函数极小化问题归结为关联多面体的隶属度问题，等价于多面体上的优化问题。后一个优化问题是加权分数阶拟阵匹配问题的推广。我们通过扩展Gijswijt和Pap（2013）[9]的结果，给出了该优化问题的组合多项式时间算法。
In this paper we show the first polynomial-time algorithm for the problem of minimizing submodular functions on the product of diamonds of finite size. This submodular function minimization problem is reduced to the membership problem for an associated polyhedron, which is equivalent to the optimization problem over the polyhedron, based on the ellipsoid method. The latter optimization problem is a generalization of the weighted fractional matroid matching problem. We give a combinatorial polynomial-time algorithm for this optimization problem by extending the result by Gijswijt and Pap (2013) [9].