Indexing XML documents for XPath query processing in external memory

Qun Chen, Andrew Lim, Kian Win Ong and Jiqing Tang
Data & Knowledge Engineering
Volume 59, Issue 3, December 2006, Pages 681-699
http://dx.doi.org/10.1016/j.datak.2005.11.002

XML文書へのXPath型質問は親子関係や先祖子孫関係だけではない．
そのような質問に対する外部メモリデータ構造としてXL+-treeというものを提案して，理論的および実験的に従来の方法より優れていることを示した．

On combinatorial optimization problems on matroids with uncertain weights

Adam Kasperski and Pawel Zielinski
European Journal of Operational Research
Volume 177, Issue 2 , 1 March 2007, Pages 851-864
http://dx.doi.org/10.1016/j.ejor.2005.12.033

マトロイドの最小重み基を求める問題を考えるが，要素の重みがある閉区間に属することしか分かっていない．
いわゆる，ある種のロバスト最適化の設定．
この場合にpossibility theoryの観点から「possibly optimal base」や「necessarily optimal base」を求める問題を考える．
そして実際これらの問題を効率よく解くアルゴリズムが示されている．

ブール行列積計算のアルゴリズム

もちろん，Coppersmith-Winogradのアルゴリズムを使えばオーダーnの2.376乗で計算できるが，これは実用的でないと考えられている．
ということで，ちょっと考えたらO(n^3 / log n)という計算量のシンプルなアルゴリズムを思いついた．
「ふむ，これはなかなかいいな」と思っていたけど，これもどうやら既に知られてるらしい (Arlazarov, Dinic, Kronrod, and Faradzev 1970)．
更にO(n^3/log^2 n)時間のシンプルなアルゴリズムまで知られてるようだ (Basch, Khanna, and Motwani 1995)．
先人は偉大，ということなのか．