ISMP 1日目 続き

昨日力尽きてしまって，書けなかった分を書きます．

ゲーム理論セッションからNiv Buchbinderの「Incentives in Online Auctions and Secretary Problems via Linear Programming」．いわゆる秘書問題に対して最良の候補者を採用する確率を(漸近的に)最大にする戦略が知られていて，これはDynkin (1961) による古典的な結果であるが，候補者側からみると候補者が面接に現れる順番によって候補者の採用される確率が変わってしまう．(例えば，最初に現れた候補者はどれだけよくてもほとんど採用されない．) ということなので，順番によって採用される確率が変わらないようにするにはどうしたらよいか，ということを考えて，ある種の仮定を置くとそれが可能であることを示し，実際にそのようなアルゴリズムを提案している．解析に線形計画法を用いている．

組合せ最適化セッションからYuri Faenzaの「An O(n^4) algorithm for the maximum weighted stable set problem in claw-free graphs」．Claw-freeグラフに対して最大重み安定集合問題が多項式時間で解けるということはちょっとミステリアスではあるが，知られていた．その計算量はO(n^6)であったが，この研究ではそれをO(n^4)に改善した．基本的にはChudnovsky-Seymourによるclaw-freeグラフに対する分解定理を見て，その分解を与えるアルゴリズムとしてO(n^4)時間のものを与えることで元の問題を解くという構成を取っている．

同じく組合せ最適化セッションからFrits Spieksmaの「Coloring graphs to avoid monochromatic cycles」．与えられた有向グラフの頂点集合を2色で (properにとは限らず) 塗り，どの閉路も両方の色を持つようにできるか，という問題を考える．この研究の主結果は分枝限定的なアルゴリズムとその実験だけども，発表者自身がミクロ経済学のある論文 (Cherchye et al. 2007) にあるcollective house hold modelの結果を動機としてこの研究を行ったということが紹介されていて，それが興味深かった．