ダウンロード数: 192
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
jorsj.58.184.pdf | 201.53 kB | Adobe PDF | 見る/開く |
タイトル: | MONOTONICITY IN STEEPEST ASCENT ALGORITHMS FOR POLYHEDRAL L-CONCAVE FUNCTIONS |
著者: | Fujishige, Satoru Murota, Kazuo Shioura, Akiyoshi |
著者名の別形: | 藤重, 悟 |
キーワード: | Combinatorial optimization discrete concave function steepest ascent algorithm minimum cost flow discrete optimization |
発行日: | 23-Jun-2015 |
出版者: | Operations Research Society of Japan |
誌名: | Journal of the Operations Research Society of Japan |
巻: | 58 |
号: | 5 |
開始ページ: | 184 |
終了ページ: | 208 |
抄録: | 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. |
著作権等: | © The Operations Research Society of Japan |
URI: | http://hdl.handle.net/2433/198549 |
DOI(出版社版): | 10.15807/jorsj.58.184 |
関連リンク: | https://www.jstage.jst.go.jp/article/jorsj/58/2/58_184/_article |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。