MONOTONICITY IN STEEPEST ASCENT ALGORITHMS FOR POLYHEDRAL L-CONCAVE FUNCTIONS
-
- Fujishige Satoru
- Kyoto University
-
- Murota Kazuo
- University of Tokyo
-
- Shioura Akiyoshi
- Tohoku University
この論文をさがす
抄録
For the minimum cost flow problem, Hassin (1983) proposed a dual algorithm, which iteratively updates dual variables in a steepest ascent manner. This algorithm is generalized to the minimum cost submodular flow problem by Chung and Tcha (1991). In discrete convex analysis, the dual of the minimum cost flow problem is known to be formulated as maximization of a polyhedral L-concave function. It is recently pointed out by Murota and Shioura (2014) that Hassin's algorithm can be recognized as a steepest ascent algorithm for polyhedral L-concave functions. The objective of this paper is to show some monotonicity properties of the steepest ascent algorithm for polyhedral L-concave functions. We show that the algorithm shares a monotonicity property of Hassin's algorithm. Moreover, the algorithm finds the “nearest” optimal solution to a given initial solution, and the trajectory of the solutions generated by the algorithm is a “shortest” path from the initial solution to the “nearest” optimal solution. The algorithm and its properties can be extended for polyhedral \Lnat-concave functions.
収録刊行物
-
- 日本オペレーションズ・リサーチ学会論文誌
-
日本オペレーションズ・リサーチ学会論文誌 58 (2), 184-208, 2015
公益社団法人 日本オペレーションズ・リサーチ学会
- Tweet
キーワード
詳細情報 詳細情報について
-
- CRID
- 1390282679085765760
-
- NII論文ID
- 130005083503
-
- NII書誌ID
- AA00703935
-
- ISSN
- 21888299
- 04534514
-
- HANDLE
- 2433/198549
-
- NDL書誌ID
- 026498658
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- IRDB
- NDL
- Crossref
- CiNii Articles
- KAKEN
-
- 抄録ライセンスフラグ
- 使用不可