ダウンロード数: 255
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
130936415.pdf | 308.51 kB | Adobe PDF | 見る/開く |
タイトル: | A Min-Max Theorem for Transversal Submodular Functions and Its Implications |
著者: | Fujishige, Satoru Tanigawa, Shin-ichi |
著者名の別形: | 藤重, 悟 |
キーワード: | transversal submodular functions $k$-submodular functions submodular functions on lattices min-max relation |
発行日: | 2-Oct-2014 |
出版者: | Society for Industrial and Applied Mathematics |
誌名: | SIAM Journal on Discrete Mathematics |
巻: | 28 |
号: | 4 |
開始ページ: | 1855 |
終了ページ: | 1875 |
抄録: | Huber and Kolmogorov [Towards minimizing $k$-submodular functions, in Proceedings of ISCO 2012, Lecture Notes in Comput. Sci. 7422, Springer, Heidelberg, 2012, pp. 451--462] introduced a concept of $k$-submodular function as a generalization of ordinary submodular (set) functions and bisubmodular functions and obtained a min-max theorem for the minimization of $k$-submodular functions. Also Kuivinen [Discrete Optim., 8 (2011), pp. 459--477] considered submodular functions on (product lattices of) diamonds and showed a min-max theorem for the minimization of submodular functions on diamonds. In the present paper we consider a common generalization of $k$-submodular functions and submodular functions on diamonds, which we call a transversal submodular function (a t-submodular function, for short). We show a min-max theorem for the minimization of t-submodular functions in terms of a new norm composed of $\ell_1$ and $\ell_\infty$ norms. This reveals a relationship between the obtained min-max theorem and that for the minimization of ordinary submodular set functions due to Edmonds [Submodular functions, matroids, and certain polyhedra, in Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications, R. Guy, H. Hanani, N. Sauer, and J. Schönheim, eds., Gordon and Breach, New York, 1970, pp. 69--87].We also show how our min-max theorem for t-submodular functions can be used to prove the min-max theorem for $k$-submodular functions by Huber and Kolmogorov and that for submodular functions on diamonds by Kuivinen. Moreover, we show a counterexample to a characterization, given by Huber and Kolmogorov [Towards minimizing $k$-submodular functions, in Proceedings of ISCO 2012, Lecture Notes in Comput. Sci. 7422, Springer, Heidelberg, 2012, pp. 451--462], of extreme points of the $k$-submodular polyhedron and make it a correct one by fixing a flaw therein. |
著作権等: | © 2014, Society for Industrial and Applied Mathematics |
URI: | http://hdl.handle.net/2433/191193 |
DOI(出版社版): | 10.1137/130936415 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。