A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER A FINITE JUMP SYSTEM
A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER A FINITE JUMP SYSTEM
复制标题
有限跳跃系统上最小化可分离凸函数的贪心算法
DOI：
10.15807/jorsj.38.362
复制
发表时间：
1995
影响因子：
--
通讯作者：
T. Naitoh
中科院分区：
文献类型：
--
作者：
Kazutoshi Ando;S. Fujishige;T. Naitoh
给出了有限跳系统（E，F）上极小化可分凸函数的贪婪算法，其中E是有限非空集，F是ZE中满足交换公理的有限非空整点集.跳跃系统的概念是由A. Bouchet和W. H.坎宁安跳跃系统是整双子模多面体、整多拟阵、（多）伪拟阵和δ-拟阵的推广，具有良好的组合性质。该算法从一个任意可行解开始，当前可行解以贪婪的方式逐步向最优解移动。我们还表明，贪婪算法终止后，最多改变一个初始可行解
We present a greedy algorithm for minimizing a separable convex function over a finite jump system (E, F), where E is a nonempty finite set and F is a nonempty finite set of integral points in ZE satisfying a certain exchange axiom. The concept of jump system was introduced by A. Bouchet and W. H. Cunningham. A jump system is a generalization of an integral bisubmodular polyhedron, an integral polymatroid, a (poly-)pseudomatroid and a delta-matroid, and has combinatorially nice properties. The algorithm starts with an arbitrary feasible solution and a current feasible solution incrementally moves toward an optimal one in a greedy way. We also show that the greedy algorithm terminates after changing an initial feasible solution at most