Article ID: | iaor19961042 |
Country: | Japan |
Volume: | 37 |
Issue: | 3 |
Start Page Number: | 188 |
End Page Number: | 196 |
Publication Date: | Sep 1994 |
Journal: | Journal of the Operations Research Society of Japan |
Authors: | Fujishige Satoru, Ando Kazutoshi, Naithoh Takeshi |
Keywords: | optimization, programming: integer |
The authors present a new greedy algoritm for minimizing a separable convex function over an integral bisubmodular polyhedron. The algorithm starts with an arbitrary feasible solution and a current feasible solution incrementally moves toward an optimal one in a greedy way. The authors 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.