# Finite Playground

## New improvement to fast matrix multiplication

Again the exponent for the fastest matrix multiplication algorithm is improved.  This time the magical number is 2.3728639, 0.0000630 better than Williams’ 2.3729269.  (Last time it goes from the famous CW bound 2.3754770 to Stothers’ 2.3736898 then to Williams’, a 0.0025501 improvement.)

Powers of Tensors and Fast Matrix Multiplication, François Le Gall, 2014.

## Practice on maximum coverage problem

Recently I just realized that the analysis of approximation algorithms of covering typed problems are unintuitive to me.  I don’t know whether it’s because the analysis-based nature which always gets me, or there’s just that I’m not familiar with the proof enough.  In any case, this is my attempt on decoding the proofs.  Let me take maximum coverage problem as an example, which given a set system with a number $k$, we ask what is the largest amount of elements we can cover using $k$ sets.

Theorem.  Greedy covering gives a $(1-1/e)$-approximation to the maximum coverage problem.

Proof.  Let $\textit{new}(i)$ be the number of elements newly covered at step i.  Let $\textit{covered}(i)$ be the number of elements covered from step $1$ to step $i$; we have

$\textit{covered}(i) = \textit{new}(1) + \dots + \textit{new}(i)$

Let $\textit{gap}(i)$ be the number of elements we still need to cover in order to cover opt elements; therefore $\textit{gap}(i) = \textit{opt} - \textit{covered}(i)$.

Key observation.  At step $i$, there is always a set that covers at least $k$-th fraction of the uncovered elements in $\textit{OPT}$.
Proof.  This is exactly the part I feel uncomfortable with; I find the following formulation helps my intuition:
“No matter the removal of any subset of elements in $\textit{OPT}$, the original $k$ sets in the optimal cover still covers $\textit{OPT}$; and because $k$ sets are enough to cover a partial of $\textit{OPT}$, there is one set among the $k$ sets that covers at least $k$-th fraction of the partial $\textit{OPT}$.”

Therefore $\textit{new}(i) \ge \textit{gap}(i-1)/k$; from this point on things becomes easy.

$\textit{gap}(i) \le \textit{gap}(i-1) - \textit{gap}(i-1)/k = {k-1 \over k} \textit{gap}(i-1)$,

so each step will shrink the gap by $(k-1)/k$.  After $k$ steps the gap has size at most $(1-1/k)^k \le 1/e$-th fraction of $\textit{opt}$, which proves the statement.

## Maximum matching in general graphs

RandMatching(G), G 為 n-node m-edge graph.
1. 令$M_0$為任意 matching. 令$p = 2^m$.
2. 執行底下迴圈$k=10m \log n$次, 迴圈參數為$i$:
2.1 隨機選取一個邊$e$.
2.2 令$M'$$\frac{p}{1+p}$的機率是$M_i \cup \{e\}$, 有$\frac{1}{1+p}$的機率是$M_i \setminus \{e\}$.
2.3 假如$M'$是個 matching, 則令$M_{i+1} = M'$; 不然就還是讓$M_{i+1} = M_i$.
3. 輸出$M_k$, 程式結束.

## Random stuff, 110629

• Triangle detection
很久很久之前讀過的 triangle detection. 用到了弱化的$\epsilon$-net theorem.
結果: sub-cubic triangle detection 等價於 sub-cubic All-pair shortest path(!), 更 imply sub-cubic Boolean matrix multiplication(!!)
學習組合最優化 (combinatorial optimization) 與計算幾何 (computational geometry). 首先接觸的是 additive spanner 問題; S. Baswana et al. 的論文可以當作不錯的 survey.
簡單的學了 additive 6-spanner 的構造, 精神上就是 clustering.
結果: 任何圖會有個$O(n^{4/3})$-size additive 6-spanner. Sublinear-size $(1+\epsilon)$-multiplicative spanner 有多種構造法.
• Geometric set cover
然後就開始碰 geometric hitting set problem. 讀了 On the Set Multi-Cover Problem in Geometric Settings, 把 set multi-cover 問題 reduce 到一般的 set cover, 得到一個$O(\log \mathsf{opt})$-approximation 演算法. 而 set cover 一般來說只有標準的$O(\log n)$-approximation, 利用 bounded VC-dimension 配上$\epsilon$-net theorem (又是它!) 可以得到上面的 bound.
而對於 maximum coverage problem, 標準的解是個$1-1/e \approx 0.632$-approximation. 想要解所謂的 maximum 2-coverage problem, 也就是要 maximize 被蓋到兩次以上的點; 因為要 optimize 的函數喪失了 submodular 的性質, 因此目前沒有任何不單純的 upper bound.
• Girth on planar graphs
關於平面圖, 老師和我寫的 Computing the Girth of a Planar Graph in Linear Time 上了 COCOON’11. 一張圖的 girth 是指圖中最小圈的大小.
• Minimum cut on planar graphs
最近這個問題被解到$O(n \log\log n)$ time. 其中 C. Wulff-nilsen 用 r-division, multiple source shortest-path 與 fast Dijkstra 解掉了很多平面圖上的問題, 但經過近半年的嘗試, 似乎這是現在技巧的極限.
在 unweighted graph 上蛋蛋和我提出一個關於 planar distance preserver 的猜想, 不過仍然不知道怎麼處理.
• Diameter on planar graphs
現在嘗試改解 diameter problem. 一張圖的 diameter 圖中最長的 shortest path 的長度. 在 general graph 上人們相信這跟 All-Pair shortest path 一樣難, 但在平面圖上 C. Wulff-nilsen 可以解到$o(n^2)$, 因此說不定比較容易. 還在熟悉 diameter 的性質當中!
• Even/odd hole detection
努力的寫作 even hole detection 論文中, 目前的時間似乎是$O(n^{10})$. 總覺得分析越多結構結果會越好, 但論文複雜度就越高; 似乎是個可以很容易得到 lower bound 的問題? 但沒有看到人做過.
讀了 Odd Hole Recognition in Graphs of Bounded Clique Size, 技巧跟當初 P. Seymour et al. 的 even hole detection 差不多, 只是在 odd hole 上的結構較弱, 最主要的問題是 clique 大小可以很大!
然後讀了證明 odd hole through one node 是 NP-complete 的證明; 試著想要去掉那個一定要經過的 node, 還沒有完全看出問題所在. Odd hole detection 永遠會是目標之一!

(to be continued…)

## Shortest paths in graphs with integral weights

Thorup ’03, directed graphs, $O(m + n \log\log n)$, by integral priority queue
Thorup ’99, undirected graphs, $O(m)$, by hierarchical bucketing.

van Emde Boas ’77, $O(m \log\log C)$,
Thorup ’03, $O(m + n \log\log C)$.

Survey: Zwick ’01.