一人輪講
V. Braverman and A. Meyerson, “Streaming k-means on well-clusterable data,” In SODA, 2011.ストリームk-meansアルゴリズム．
Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman and Angela Y. Wu. A Local Search Approximation Algorithm for k-Means Clustering. In Proceedings of the eighteenth annual symposium on Computational ge…
David Arthur and Sergei Vassilvitskii, k-means++: The Advantages of Careful Seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms (2007), pp. 1027-1035.言わずと知れたk-meansアルゴリズム（Lloydのアルゴリ…
K. Hajebi, Y. Abbasi-Yadkori, H. Shahbazi, and H. Zhang, Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph. ;In Proceedings of IJCAI. 2011, 1312-1317. k近傍グラフ上での山登り方による近似最近傍探索． Locality Sensitive …
Michael Shindler, Alex Wong, and Adam Meyerson. Fast and Accurate k-means For Large Datasets. In NIPS, 2011.k-meansアルゴリズムのストリーム版で，割りと最近のもの．今回は適当に紹介．
David Pearson, A Polynomial-time Algorithm for the Change-Making Problem, Technical Report TR 94-1433, 1994.コインの両替問題のインスタンスについて，貪欲法が常に最適解を返すかどうかをで判定する．更に，答えが"NO"の場合は，最適解と貪欲解が一…
A. Björklund and T. Husfeldt. Inclusion--Exclusion Algorithms for Counting Set Partitions. FOCS 2006.ほったらかしにしてた続き． 多項式空間 前回の方法では，空間計算量は指数オーダーだったが，空間計算量を節約して多項式オーダーに収める事が出来…
A. Björklund and T. Husfeldt. Inclusion--Exclusion Algorithms for Counting Set Partitions. FOCS 2006.備忘録がてら記事を書いていたら長くなったのでとりあえずPart 1．http://d.hatena.ne.jp/wata_orz/20120329 にて彩色数をで求めるアルゴリズムの論…
