A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER AN INTEGRAL BISUBMODULAR POLYHEDRON
A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER AN INTEGRAL BISUBMODULAR POLYHEDRON
复制标题
积分双子模多面体上可分离凸函数最小化的贪心算法
DOI：
10.15807/jorsj.37.188
复制
发表时间：
1994
影响因子：
--
通讯作者：
T. Naitoh
中科院分区：
文献类型：
--
作者：
Kazutoshi Ando;S. Fujishige;T. Naitoh
我们提出了一种新的贪婪算法，用于最小化积分双次方多面体上的可分离凸函数。该算法从一个任意可行解开始，当前的可行解以贪婪的方式逐步走向最优解。\我们还证明，如果一个可行解不是最优解，那么在坐标陡降方向上至少存在一个最优解。
We present a new greedy algorithm for minimizing a separable convex function over an integral bisubmodular polyhedron. The algorithm starts with a.n arbitrary feasible solution and a current feasible solution incrementally moves toward an optimal one in a greedy way. \Ve also show that there exists at least one optimal solution in the coordinate-wise steepest descent direction from a feasible solution if it is not an optimal one.