平成 25 年度第 2 回 ＯＲ横断若手の会(KSMAP)

日  時：7 月 23 日(火)
出席者: 14 人
場  所：京都大学数理解析研究所110号室 

テーマと講師：
（１）大舘陽太 (北陸先端科学技術大学院大学)
「On Low Congestion Spanning Trees」

概要: グラフの全域木の中で混雑度と呼ばれるパラメータ
を最小化するものを求める問題についてこれまでの研究成
果が報告された．外平面グラフのようなクラスのグラフに
ついては問題が線形時間でとけること，それ以外のいくつ
かのグラフクラスでは問題がNP困難であることなどが紹介
された．特に，グラフの木幅と呼ばれるグラフパラメータ
と混雑度の関係性について指摘がされた．


(2) 塩浦昭義 (東北大学)
「複数財の競り上げ式オークションにおけるワルラス均衡の計算　
— 離散凸解析に基づく計算量解析 —」

概要： 複数の入札参加者と複数の財からなるオークション
市場におけるワルラス均衡価格を求める問題について，
Ausubel (2006)による先行研究の成果が離散凸解析の観点
から解釈できることが紹介された． さらに，競り上げ式
オークションのアルゴリズムで使用される劣モジュラ関数
最小化アルゴリズムがこの問題に適用する際には高速化で
きることなどが報告された．