Home of Mr. 5

文献：Graham Cormode, S. Muthukrishnan, and Ke Yi. 2011. Algorithms for distributed functional monitoring. ACM Trans. Algorithms 7, 2, Article 21 (March 2011), 20 pages.

文献：Computational Complexity: a Modern Approach

从开学以来一直忙到生理上呕吐，各个项目全都搁置了，现在觉得必须赶紧捡起来，至少把之前想过的有用的小定理记录下来。

这篇blog谈论为什么有完美匹配的二部图对于在线匹配算法是最难的。（特指对于绝大多数贪心算法）换句话说，在我们分析C.R.时，只需要关心这一类图。

文献：On Approximately Fair Allocations of Indivisible Goods

这篇文章应该算是不可分割物品公平分配的奠基作，

这篇blog暂时只谈这篇文章的第一个结果。

Online Bipartite Matching with Reusable Resources这篇文献里有两个比较重要的open problem。

1. RANKING算法在该模型下怎么分析C.R.

2. 该模型下的最佳C.R.是多少，有可能达到吗？

就我目前的、尚未验证正确性的证明来看，这两个问题的答案是：该模型下的最佳C.R.就是，而且RANKING算法就可以达到。（更新后该结果不确定是否能得到）

本文译自Existence of functions with exponential circuits complexity，原作者David Steurer。有删改。

本文所述定理由C. E. Shannon于1949年在The synthesis of two-terminal switching circuits提出。

在研究的时候鼓捣出来一些好玩的东西。