ダウンロード数: 201
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
j.disopt.2013.12.001.pdf | 311.68 kB | Adobe PDF | 見る/開く |
タイトル: | Generalized skew bisubmodularity: A characterization and a min–max theorem |
著者: | Fujishige, Satoru Tanigawa, Shin-ichi ![]() Yoshida, Yuichi |
著者名の別形: | 藤重, 悟 |
キーワード: | Skew bisubmodularity Submodularity Convex extensions |
発行日: | May-2014 |
出版者: | Elsevier B.V. |
誌名: | Discrete Optimization |
巻: | 12 |
開始ページ: | 1 |
終了ページ: | 9 |
抄録: | Huber, Krokhin, and Powell (2013) introduced a concept of skew bisubmodularity, as a generalization of bisubmodularity, in their complexity dichotomy theorem for valued constraint satisfaction problems over the three-value domain. In this paper we consider a natural generalization of the concept of skew bisubmodularity and show a connection between the generalized skew bisubmodularity and a convex extension over rectangles. We also analyze the dual polyhedra, called skew bisubmodular polyhedra, associated with generalized skew bisubmodular functions and derive a min–max theorem that characterizes the minimum value of a generalized skew bisubmodular function in terms of a minimum-norm point in the associated skew bisubmodular polyhedron. |
著作権等: | © 2014 Elsevier B.V. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 This is not the published version. Please cite only the published version. |
URI: | http://hdl.handle.net/2433/185325 |
DOI(出版社版): | 10.1016/j.disopt.2013.12.001 |
出現コレクション: | 学術雑誌掲載論文等 |
![](/dspace/image/articlelinker.gif)
このリポジトリに保管されているアイテムはすべて著作権により保護されています。