The DIMACS Implementation Challenge

The 9th DIMACS Implementation Challengeはすでに昨年の秋に終了しているのだが、最短路問題が課題になっていた。最近の最短路問題に対するアルゴリズムは、いかに最適性を保証しながらネットワークを簡略化するかに焦点が行われていて、前処理の部分はそれなりに時間がかかっても良いとされる。そのかわり実際に２点を入れたときの最短路の距離計算は非常に高速であることが望まれている(msec 以下)。前処理で事前に全ての最短路を求めれば良さそうさが、それでは大きなネットワークではメモリに入りきらないので、結局 msec という単位での返答は難しい。アルゴリズムを見ているとここまでやるかという感じもするが、それもまた面白い。
2000年には SDP を課題とする The 7th DIMACS Implementation Challenge が開催された。これには参加したのだが、現在ぐらいのソフトウェアの手持ちがあれば尚良かったのにと思う。またこのような機会があるだろう。