KSMAP 琵琶湖合宿

今年も KSMAP 合宿へ参加してきた。去年に比べ関東勢が非常に多く非常に盛り上がった印象である。

今回は質疑応答の時間をゆっくり取れると思い、ポスター発表に切り替えた(去年は講演)。なかなか情報技術系の知識も要求される内容なので、あまり期待をしていなかったが思った以上に興味を持っていただいた印象。ありがたいです。

滋賀県彦根市は "ひこにゃん"という緩キャラと、ボードゲームの一種カロムが盛んな街。

理論的計算量と実験的性能 Heap と mbp

heap と mbp が同様の性能になるという話。

heap : Binary Heap, SSSP O((m+n)log(n))
mbp : Multi-Level Buckets, SSSP O(m+nlog(U))


まず heap の計算量から考えてみよう。
insert(), decreasekey(), extractmin() の計算量は1回あたり log(n) となっている。この log(n) の n はヒープサイズの最大値となっており、最悪時には n となるが、点数 2400万 の USA でもこの値は 10000 程度と随分小さい。

2400 万と 1 万では随分差があるように見えるのだが、あるグラフを与えられたとき、優先キュー内に格納される点数の最大値を簡単に求める方法はない。点数や枝数や次数には緩く依存しているが、ほとんど定数として考えても良さそうである。経験的に道路ネットワークのように近い点同士が枝を張るようなPlanar graph では優先キュー内の要素数が大きくなりがちである。また次数が非常に大きくなる場合も同様である。


次に mbp の計算機上での実行について詳しく見ていく。
mbp 内に格納されるデータアクセスパターンを見ていくと 2^n により分類されている。このアクセスがある意味 heap のような木構造のアクセスパターンと良く似ており、この不連続のアクセスに性能が依存していると考えられる。また mbp のメモリバンド幅要求は非常に大きいが、最適化した heap ではある程度抑えられている。


これらから、アルゴリズムの限界と考えても良いのだが、現状としては多くの要因によってたまたま fitting しているように見えてるだけとかいえないだろう。

講演

Timo Berthold さんによるご講演。

SCIP の開発思想は非常に明確であり、共感するところが非常に多い。特に plugin として新たな問題形式を追加することで、多くの問題形式に対応できるという非常に柔軟なところがすばらしい。また、制約条件などを見て変数や制約がどの level (knapsack, binary, lp, ip など)なのか判断しており、条件が揃えばより簡単な問題として解いているようだ。

開発は C 言語で行っており、configure は好きではないようで makefile を環境毎に用意している。

Graphviz

graphviz では .dot ファイルを作成し読み込ませる事でグラフを描画する.例えば次のような foo.dot では, 5点8枝のグラフを記述することができる. 枝 label があるとかなり動作が重くなるようで,大きなものを描きたい場合はない方がよいだろう. といっても数千点ほどの規模でもうまくいかない.

digraph foo {
  1 -> 2 [ label = "4" ];
  1 -> 3 [ label = "5" ];
  2 -> 3 [ label = "8" ];
  2 -> 4 [ label = "2" ];
  2 -> 5 [ label = "15" ];
  3 -> 4 [ label = "10" ];
  3 -> 5 [ label = "6" ];
  4 -> 5 [ label = "9" ];
}

第3回 SCOPE

Karen Aardal さんと Timo Berthold さんによる今年 3 回目となる SCOPE。今回も多くの方がいらっしゃいました。

イノベーションジャパン2010

イノベーションジャパンへの出展を行った。昨年度は講演のみだったので、なかなか企業の方と触れる機会が少なかったが、今回はポスターなので非常に多くの方と交流する事が出来た。3日間で300セットのビラを配り、30枚程の名刺交換をした。この数だけでも非常に有意義であった事が伺えるだろう。