文献

J-GLOBAL ID：201702268004912613   整理番号：17A1051210

L-凸関数最小化のための2段階アルゴリズムの時間限界について

Note on time bounds of two-phase algorithms for L-convex function minimization

著者 (2件)： MUROTA Kazuo (Tokyo Metropolitan Univ., Tokyo, JPN) ,  SHIOURA Akiyoshi (Tokyo Inst. Technol., Tokyo, JPN)
資料名： Japan Journal of Industrial and Applied Mathematics  (Japan Journal of Industrial and Applied Mathematics)
巻： 34  号： 2  ページ： 429-440  発行年： 2017年 
JST資料番号： L5671A  ISSN： 0916-7005  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 離散凸解析におけるL-凸関数に関する最小化アルゴリズム(2段階アルゴリズムと呼ぶ)を解析し,その反復数に関する厳密な限界を求めた。本研究の動機は,オークション理論における反復オークションにある。具体的には,TwoPhaseアルゴリズムやTwoPhaseMinMaxアルゴリズムを与えた上で,それらに関する定理を示した。

シソーラス用語： 数学 ,  *アルゴリズム ,  技術 ,  制約条件 ,  理論 ,  *最適化 ,  離散系 ,  *凸関数 ,  改変
準シソーラス用語： L1最小化 ,  オークション理論 ,  最小化 ,  時間制約 ,  凸解析 ,  反復アルゴリズム ,  離散最適化 ,  離散数学

分類 (1件)： 数値解析,近似法  (AB04000F)

引用文献 (15件)：

• Andersson, T., Erlanson, A.: Multi-item Vickrey-English-Dutch auctions. Games Econ. Behav. 81, 116-129 (2013)
• Ausubel, L.M.: An efficient dynamic auction for heterogeneous commodities. Amer. Econ. Rev. 96, 602-629 (2006)
• Blumrosen, L., Nisan, N.: Combinatorial auction. In: Nisan, N., Roughgarden, T., Tardos, É., Vazirani, V.V. (eds.) Algorithm. Game Theory, pp. 267-299. Cambridge Univ. Press, Cambridge (2007)
• Cramton, P., Shoham, Y., Steinberg, R.: Combinatorial auctions. MIT Press, Cambridge (2006)
• Demange, G., Gale, D., Sotomayor, M.: Multi-item auctions. J. Polit. Econ. 94, 863-872 (1986)

タイトルに関連する用語 (5件)： 凸関数 ,  最小化 ,  段階 ,  アルゴリズム ,  限界