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
Simulated Annealing_工学_高等教育_教育专区。Simulated AnnealingSimulated Annealing (模拟退火法)报告人:陈世明 Simulated Annealing 1 大纲 简介 攀登演算法 模拟...
Novel Adaptive Simulated Annealing Algorithm for Constrained Multi-Objective Optimization_专业资料。/专h rii j ioncnf CamuasnntCoNovel AdapiSiuledAnnealgtve mat ...
4.Simulated Annealing_计算机软件及应用_IT/计算机_专业资料。模拟退火算法Practical Optimization Algorithm Design Lesson 4: Simulated Annealing Thomas Weise Nature...
Parallel Genetic Simulated Annealing Hybrid Algorithm for Task Scheduling 隐藏>> 维普资讯 http://www.cqvip.com VoI1 No. 20 17—32. 15063818 Naur ...
A hybrid genetic-simulated annealing algorithm for optimization of hydraulic manifold blocks_专业资料。维普资讯 http://www.cqvip.com A Jhnh nEgE)20,23:6...
Genetic simulated annealing algorithm for task scheduling based on cloud computing environment_天文/地理_自然科学_专业资料。Genetic Simulated Annealing Algorithm...
Optimization by simulated annealing: A necessary and su cient condition for convergence. In Van Ryzin, J., editor, Adaptive Statistical Procedures and ...
To address the problem of the self-optimization of coverage and capacity in LTE networks, we introduce an approach based on a simulated annealing algorithm...
Leighton, \Improving the Performance of the Kernighan-Lin and Simulated Annealing Graph Bisection Algorithms," in Proc. ACM/IEEE Design Automation Conf., ...
4] T. N. Bui, \Improving the Performance of the Kernighan-Lin and Simulated Annealing Graph Bisection Algorithms", in Proc. ACM/IEEE Design Automation...
热门文档