文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Simulated Annealing for Graph Bisection
侵权投诉

Simulated Annealing for Graph Bisection

Simulated Annealing for Graph Bisection

color. A partition or bisection of G is a partition of V into sets L and R (thought of as\left" and\right") with jLj= jRj= n=2. The cut-wid

th of a bisection is the number of cut edges: jffu; vg 2 E: u 2 L and v 2 Rgj; and the bisection width of G is the minimum over all bisections (L; R) of the cut-width of (L; R). We note that a graph in Gn; 1; 1 is simply a random graph on n vertices with edge 2 2 1 1 probability 2, and that the cut-width of a random bisection has expectation 8 n2 and variance (n2) as well. It can be shown that with high probability the bisection width 1 is 1 n2? (n3=2). On the other hand if p= 2 but p? r= n?2, with 3=2<< 2, the 8 natural partition (with L the set of black vertices and R the set of white vertices) has 1 1 1 expected width 4 rn2= 1 n2? 4 (p? r)n2= 1 n2? 4 n . It can be shown 4] that with high 8 8 probability this is in fact the minimum bisection. The Metropolis process on bisections is described in detail in Section 2, but, in brief, the allowed transitions take a pair of vertices, one from each side of a bisection, and interchange them. The main new result is contained in Theorem 6.1: informally, this theorem states that with overwhelming probability the Metropolis process will converge to the unique minimum bisection in time about O(n2 ), provided> 11=6. The proof uses (in Claim 5.2) a novel argument concerning perturbed Markov chains that in a sense extends the investigations of Azar, Broder, Karlin, Linial, and Phillips 1] into biased random walks. Boppana 3] and Bui 5] consider a Gnmb model, where graphs are chosen uniformly from the set of n-vertex graphs with m edges and bisection width b. This is roughly 1 equivalent to the Gnpr model, with b= 4 rn2 and m= 1 (p+ r)n2 . In order to compare 4 the two models, de ne the de ciency of a graph to be the di erence between its bisection width and the expected cut-width of a random bisection. For a random graph in Gnmb 1 1 the de ciency is close to 2 m? b, whereas for the Gnpr model it is typically 8 n O(n). Boppana presents an algorithm which with probability 1? O(n?1 ) nds the minimum 1 5p bisection for graphs in Gnmb with 2 m? b 2 mn log n, and sets as an open problem the average-case performance of simulated annealing (as well as the Kernighan-Lin and greedy heuristics). The range of applicability of Boppana's algorithm is exceptionally wide, taking in graphs whose de ciency is close to the threshold where the planted bisection becomes lost amongst other random small bisections. In this regard, our result compares unfavorably, since the expected de ciency is required to be substantially higher: O(n11=6+") against p (n3=2 log n ) for dense graphs. Nevetherless, it is perhaps surprising that an algorithm as simple as that of Metropolis can provably deal with de ciencies of order n with< 2. It is worth observing that Boppana's algorithm is by no means simple to implement, requiring as it does the Ellipsoid Method as a subroutine, whereas the Metropolis process is trivial. The Metropolis algorithm for minimum bisections is also fast: faster even than Theorem 6.1 would suggest.

As will be apparent later, the algorithm burns up almost all its alloted time in a rather mindless way after the minimum bisection has already essentially been found; by slightly modifying the choice of perturbations the execution time could easily be reduced to O(n1+" ). For sparse graphs (p n?1=6) our results become vacuous. This is broadly in line with 3

上一页第3页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email