(C) グラフ最適化問題に対する厳密解法および近似解法の設計
本研究室では様々な組合せ最適化問題について研究を行っています．以下では，その中から「組合せオークション」について説明します．
オークションは，出品物に対し複数の購入希望者が入札を行い，最高値の入札をした者が落札するという商取引です．
組合せオークションは，複数の商品が出品されているときに「商品Aと商品Bをセットで１万円で欲しいが，片方だけならば要らない」とか，
「商品Aを１万円で，あるいは商品Bを８千円で欲しいが，両方は要らない」といった入札を許すようなオークションです．
合計額が最大となるような入札を行った人達が落札者となります．
例えば，パソコンA，パソコンB，プリンターが出品されていて，以下のような入札があるとします．
・ 太郎さんはパソコンAとプリンターをセットで１５万円の入札
・ 次郎さんはパソコンAを１０万円か，パソコンBを８万円のいずれかでという入札
・ 花子さんはパソコンBとプリンターをセットで１４万円の入札
ここでは，誰が落札するかを仮定し，その際の合計金額を計算してみます．
・ 太郎さんと次郎さんが落札 ： 次郎さんはパソコンBを手に入れ，合計が２３万円となる．
・ 花子さんと次郎さんが落札 ： 次郎さんはパソコンAを手に入れ，合計が２４万円となる
・ 太郎さんと花子さんが落札 ： 二人ともプリンターが欲しいのでこの組合せはない．
・ 一人だけが落札 ： 最高でも太郎さんの１５万円である．
よって，上記の入札ならば落札者は次郎さんと花子さんということになります．
上の例では落札者の計算が手作業でできますが，出品物や人数が増えると急激に計算時間が増えてしまいます．
このことは組合せ爆発と呼ばれています．
組合せ爆発が起きるような問題に対しては，組合せ爆発をできるだけ回避するように最適解を求める方法（厳密解法）の研究と，
最適解を求めるのを諦め，比較的良い解を求める方法（近似解法）の研究があります．本研究室では，様々な問題に対する
厳密解法や近似解法の開発を行っています．
［発表論文］
・ “An exact algorithm for the maximum weight K3-free subgraph problem,” Proc. World Congress on Engineering 2008, pp.834-837 (2008).
・ “A new exact algorithm for the maximum weight clique problem,” Proc. 23rd International Technical Conference on Circuits/Systems, Computers and Communications, pp.317-320 (2008).
・ “局所探索法による階層的描画の辺交差削減” 電子情報通信学会論文誌(A), vol. J92-A, pp. 55-61 (2009).
など