Finite Playground

To verify is human; to prove, divine.


5 Comments

Random stuff, 110629

最近讀了不少東西, 但都沒有花時間寫下來… 實在是個不好的習慣 :S
趁現在作一些速記! 希望有機會寫成文章… 囧

    • Triangle detection
      很久很久之前讀過的 triangle detection. 用到了弱化的\epsilon-net theorem.
      結果: sub-cubic triangle detection 等價於 sub-cubic All-pair shortest path(!), 更 imply sub-cubic Boolean matrix multiplication(!!)
    • Additive spanner
      學習組合最優化 (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…)


Leave a comment

Discrepancy theory

Let (V,\mathcal{S}) be a set system with V = [n] and \mathcal{S} \subseteq 2^{[n]}. A ±1-coloring is a mapping \chi : [n] \to \{1,-1\}. The discrepancy of a set system (V,\mathcal{S}) is defined as

\displaystyle{\text{disc}(S) = \min_{\chi} \{\max_{S \in \mathcal{S}} |\chi(S)|} \},

where \chi(S) = \sum_{i \in S} \chi(i).

General bounds:
– Spencer ’85, Six standard deviations suffice, O(\sqrt{n \log (2|\mathcal{S}|/n)}).

If every element appears in at most t sets,
– Beck-Fiala ’81, “Integer-making” theorems, O(t).
– Srinivasan ’97, Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems, O(\sqrt{t} \log n).
– Banaszczyk ’98, Balancing vectors and Gaussian measures of n-dimensional convex bodies, O(\sqrt{t \log n}).

Constructive bounds:
– Bansal ’10, Constructive algorithms for discrepancy minimization.


Leave a comment

Shortest paths in graphs with integral weights

發現每次寫文章都因為希望講完整, 寫的很長因此很花時間, 久了就開始懶了.
因此, 新增一個 “速記” 分類, 用來記錄一些想要寫下來但不想整理的東西 XDD

目前看到在 integral weights 上解 Shortest paths 的方法有:
Thorup ’03, directed graphs, O(m + n \log\log n), by integral priority queue
Thorup ’99, undirected graphs, O(m), by hierarchical bucketing.

如果有最大的邊重 C, 那麼
van Emde Boas ’77, O(m \log\log C),
Thorup ’03, O(m + n \log\log C).

Survey: Zwick ’01.