imported>Etone |
imported>Etone |
Line 1: |
Line 1: |
| == Problem 1== | | =Count Distinct Elements= |
| 一个<math>k</math>-超图 (<math>k</math>-uniform hypergraph) <math>\mathcal{H}\subset{[n]\choose k}</math> 的 '''blocking set''' 是这样一个集合 <math>T\subseteq[n]</math>,使每一个超边 (hyper-edge) <math>S\in\mathcal{H}</math> 都有 <math>T\cap S\neq\emptyset</math>。
| |
|
| |
|
| 注:当 <math>k=2</math> 的时候,<math>\mathcal{H}</math> 就是一个图,而 blocking set <math>T</math> 就是这个图的顶点覆盖(vertex cover)。因此,blocking set 就是顶点覆盖在超图(hypergraph)上的推广。我们知道最小定点覆盖(minimum vertex cover)问题是 NP-hard 问题,因此求最小 blocking set 也是难的。
| | == An estimator by hashing == |
|
| |
|
| 证明:任何 <math>\mathcal{H}\subset{[n]\choose k}</math>, <math>|\mathcal{H}|=m</math>,都存在一个不大于 <math>\left\lceil\frac{n\ln m}{k}\right\rceil</math> 的 blocking set。
| | ==Flajolet-Martin algorithm== |
|
| |
|
| == Problem 2== | | = Set Membership= |
| 一个图 <math>G(V,E)</math> 的'''支配集''' (dominating set) 是一个顶点集合 <math>D\subseteq V</math>,使得每个顶点 <math>v\in V</math> 要么属于 <math>D</math> 要么有邻居属于 <math>D</math>。最小支配集 (minimum dominating set) 是 NP-hard问题。
| |
|
| |
|
| 证明:任何一个 <math>n</math> 个顶点的 <math>d</math>-regular 图(每个顶点恰好有 <math>d</math> 个邻居),必然存在一个不大于 <math>\frac{n(1+\ln(d+1))}{d+1}</math> 的支配集。
| | == Perfect hashing== |
|
| |
|
| == Problem 3 == | | == Bloom filter == |
| <math>H(W,F)\,</math> 为一个图,<math>n>|W|\,</math> 为一个整数。已知存在一个图 <math>G(V,E)\,</math> 有 <math>|V|=n, |E|=m\,</math> 且<font color=red>不包含</font> <math>H\,</math> 子图。
| |
|
| |
|
| 证明:对于 <math>k>\frac{n^2\ln n}{m}</math>,存在一个对 <math>K_n\,</math>(<math>n</math>结点完全图)的<font color=red>边</font>的 <math>k</math> 着色,没有单色(monocharomatic)的<math>H\,</math>。
| | = Frequency Estimation= |
|
| |
|
| 注:令 <math>K_n</math> 的边集为 <math>E={V\choose 2}</math>,“对 <math>K_n</math> 的边的 <math>k</math> 着色",就是一个映射 <math>f: E\rightarrow [k]</math>。
| | == Count-min sketch== |
| 即,每个边选择 <math>k</math> 种颜色之一进行着色,可以任意着色,无需考虑相邻的边是否同色。
| |
| | |
| == Problem 4 == | |
| 令 <math>\mathcal{H}\subseteq{[n]\choose k}</math> 为一个 <math>k</math>-uniform <math>k</math>-regular hypergraph,即 <math>\forall i\in[n]</math>,刚好有 <math>k</math> 个不同的 <math>S\in\mathcal{H}</math> 满足 <math>i\in S</math>。
| |
| | |
| 假设 <math>k\ge 10</math>。证明:存在一个对 <math>[n]</math> 的 2着色 <math>f:[n]\rightarrow\{0,1\}</math> 使得 <math>\mathcal{H}</math> 中不存在单色的集合 <math>S\in\mathcal{H}</math>。
| |