Finite Playground

To verify is human; to prove, divine.

Random stuff, 110629

5 Comments

最近讀了不少東西, 但都沒有花時間寫下來… 實在是個不好的習慣 :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…)

Author: hcsoso

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.

5 thoughts on “Random stuff, 110629

  1. 很少见到需要O(n^c)的算法. c>5.
    查了一下…最早竟然要O(n^40).

    你是本科生毕业么? 好强啊… 有压力…

    • 歡迎! 竟然有人在看我的 blog 讓我感到很榮幸 :D
      這類的問題的確是不多, 不過我還有看過更誇張的 :P
      看看這篇論壇的討論, 我想你會很有興趣!

      我是 CS 畢業的學生, 我的興趣在 TCS 跟 Math 的交界之處.
      看了你的 blog 發現我們興趣很類似, 很高興看到同行! 喜歡 TCS 的人真的不多呢, 看起來你蠻熟悉代數的? 代數與計算理論這方面有許多問題很有趣, 希望未來有機會認識你 :) 歡迎常來逛逛!

      • 我会常来!(subscribe了)

        啊, 这个暑期在一个undergraduate research program… 搞得东西是代数和计算理论.
        真正懂得还不够多>.<…

      • 我在看Erickson的学生的时候发现了你的名字感觉好熟悉. 查了下发现啊就是你啊.
        我是UIUC的新的theory phd. 应该是想做comp geo/topo. 我们可能要成为academic brother了. xD

      • 過了好久回頭看到這篇, 希望我們能一起做出些好研究 :D

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s