A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER AN INTEGRAL BISUBMODULAR POLYHEDRON
Kazutoshi Ando, Satoru Fujishige, Takeshi Naitoh · Journal of the Operations Research Society of Japan · 1994
We present a new greedy algorithm for minimizing a separable convex function over an integral bisubmodular polyhedron. The algorithm starts with an arbitrary feasible solution and a current feasible solution increment,ally moves toward an optimal one in a greedy way. We 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.