文献

J-GLOBAL ID：201202286249099625   整理番号：12A1064295

劣モジュラ制約下におけるオンライン予測

Online Prediction under Submodular Constraints

著者 (5件)： SUEHIRO Daiki (Kyushu Univ.) ,  HATANO Kohei (Kyushu Univ.) ,  KIJIMA Shuji (Kyushu Univ.) ,  TAKIMOTO Eiji (Kyushu Univ.) ,  NAGANO Kiyohito (Univ. Tokyo)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 112  号： 83(IBISML2012 1-12)  ページ： 15-22  発行年： 2012年06月12日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本論文では離散構造のオンライン予測問題を考える。ただし,各離散構造は劣モジュラ基多面体の頂点で表現できると仮定する。例として,全域木や,順列のオンライン予測問題がある。一般的に基多面体の端点は指数個存在するが,本論文では多項式時間オンライン予測アルゴリズムを提案し,リグレットの評価を与える。特に,劣モジュラ関数が入力のサイズのみに依存するとき,提案アルゴリズムの1つはO(n²)時間で動作する。(著者抄録)

シソーラス用語： 予測 ,  *回線接続 ,  計算理論 ,  時間 ,  分解 ,  多面体 ,  頂点 ,  スパンニング木 ,  順列 ,  組合せ ,  最適化 ,  *アルゴリズム
準シソーラス用語： *オンライン ,  全域木 ,  多項式時間 ,  *予測アルゴリズム

分類 (1件)： 数理計画法  (KA03030M)

引用文献 (19件)：

• BOYD, S. Convex Optimization. 2004
• CESA-BIANCHI, N. Combinatorial Bandits. Proceedings of the 22nd Conference on Learning Theory, 2009. 2009
• CHOPRA, S. On the spanning tree polyhedron. Operations Research Letters. 1989, 8, 1, 25-29
• EDMONDS, J. Submodular functions, matroids, and certain polyhedra. Combinatorial Structures and Their Applications, 1970. 1970, 69-87
• EDMONDS, J. Matroids and the greedy algorithm. Mathematical Programming. 1971, 1, 1, 127-136

タイトルに関連する用語 (3件)： 制約 ,  オンライン ,  予測