Archive for September, 2011

“哥哥,我想你了”

September 21, 2011

家裡能上網了,想起好幾天沒跟家裡聯系,怕父母在 QQ 上留言給我,於是便登陸了半個月沒上過的 QQ。

他們沒留言給我,倒是我表弟留言給我,說已經在大學城上學了。突然覺得時間過得很快,當年我在北中上學的時候,他還在小學。現在他已然從北中畢業並且上大學了。

隨便說了幾句話,由於他有事要走了,於是便準備道別。最後他說,“哥哥,我想你了”。

雖然是很普通的一句話,不過由於從一個男性口中發出,不由得讓我感到很肉麻…… 但是同時也感到很溫馨。

父母從來都不是善於表達感情的人,潛移默化,我甚至也沒對他們說過一句“想你”的話,更無論其他人。

也許表弟比我更善於表露感情罷了。但換過來想,如果這句話由我口中冒出,也許那已經是我情感近乎崩潰的時候,說出這句話的時候,必然正是淚流滿面。

來美國不知不覺已經一年有餘,果然是人越大越心煩,因為要處理的事情越來越多。特別是在異國他鄉,事無鉅細,都要自己一人包辦。

房租、電話、銀行、網絡、水電、油費、騎車、課程、研究,單單是 name 已經可以 name a few,繼續 enumerate 下去可以嘮叨一天。

於是忙得甚至沒有時間去寫篇 blog,於是忙得週末從來也不出門,於是忙得一星期也沒有彈一次琴打一次球,於是忙得一星期也沒有關心家人一次。

一直很怕跟人 keep in touch 會浪費時間,這也的確如此。我相信五分鐘已經可以讓對方感覺到你在關心他,但理想狀況往往達不到,往往需要半個小時才能把近況說清楚。

而家人與朋友那麼一大把,實在很難勻出時間來分給他們。不是我自私,而是實際情況就是這樣的。感覺給家裡電話、視頻已經是我的極限。

所以我的朋友們,不是我我不關心大家,而是家人已經優先了。

於是朋友大概會越來越少罷。

Advertisements

Survey on Network Reliability Problem

September 8, 2011

The network reliability problem ask one to determine the survival/failure probability of some terminals in a probabilistic network. In particular, the network is given as a graph, either directed or undirected. Each edge is associated with failure (survival) probability q_e (p_e = 1-q_e), which means it will fail (survive) with probability q_e (p_e). The problem ask you to compute the failure/survival rate of some terminals. The simplest version is s-t reliability, where the terminal sets contains only two terminals. Other variants include k-terminal and all-terminal reliability. The problem is known to be hard: it is #P-complete. It remains hard even when the graph is directed acyclic with maximum degree three. No computational effective methods exist unless P=NP. Hence people are interested in finding approximation algorithms.

Last semester I wrote an survey for the problem as a project in Approximation Algorithm course. The article introduces three methods for the problem, all of them utilize Monte-Carlo as the basic framework.

1. R. Karp and M. Luby’s Monte Carlo [Karp and Luby]
R. Karp and M. Luby showed that Monte Carlo algorithm is an FPRAS (Fully polynomial time randomized approximation scheme) when the number of samples are sufficiently small. Furthermore, the number of samples are linear to the ratio of the size of positive samples and size of the sample space. Hence, how to formulate the sample space becomes the most important problem. They proposed several methods, which includes K-separating cuts, paths and cycles, and finally walks. The first two modeling is straightforward and easy to understand, however it utilized some false assumptions. The last one makes the Monte Carlo truly FPRAS. But personally I found it very hard to follow, and impractical.

2. Karger’s alpha-Minimum Cut method [Karger FPRAS]
I have to say this is an interesting and clever method. First note that the network breaks only when the failure edges are in one of the cuts. He showed that only small cuts are vital when computing the failure probability. Here `small cuts’ can be interpreted as the set of min cuts and `near’ min cuts. In another Karger’s paper, he showed that these cuts can be found can be found in polynomial time and the number is polynomial [Karger min cut] (very interesting algorithm, highly recommended). Hence, the problem can be reduced to DNF counting:

We assign a boolean variable xe to each edge e, where xe = true if e fails and false otherwise. For the ith small cut c_i, it disconnects the network if and only if all of its edges fail. Let F_i be the conjunction of all x_e, for all e in c_i. Clearly F_i is true if and only if c_i fails. Hence, the event that some small cuts fail can be written as F = disjunction of all F_i. We want to know the probability that F is true, which is clearly the failure probability of the network. Note that F is in disjunctive normal form, and the number of clauses in F is exactly the number of small cuts, which is a polynomial. There is a FPRAS for the DNF counting problem, which also uses Monte-Carlo. It is straight-forward now.

3. Zenklusen’s FPRAS for s-t reliability problem on acyclic network [Zenklusen]
This is a relatively new result. The basic idea is, in a DAG, one can compute the mean number of intact path between s and t after the failure process. In a highly unreliable network, this number is a good estimate for the s-t reliability. Monte Carlo is used to estimate the ratio between reliability(s,t) and the mean number of intact s-t paths. He showed that the s-t paths can be sampled in linear time.

[Karp and Luby]: Monte-carlo algorithms for the planar multiterminal network reliability problem.
[Karger FPRAS]: A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem.
[Karger min cut]: An O~(n^2) algorithm for minimum cuts.
[Zenklusen]: Combinatorial methods for analyzing network security and reliability

—-

I decided to release my manuscript from CS598: Approximation Algorithms, which is a survey on network reliability problem. I am not an expert on approximation algorithm, and my writing may not be so great. For any mysterious or unclear part, please refer to the original papers.

The file can be downloaded from here. The password is ‘cs598’. If this document is of any help, please give appropriate citation in your work.