Simulated Annealing for Graph Bisection
1 E A(X 0)? A(E X 0)]2 (5) G 4n2 G 1 1 0 02 (6) 2 4T EG X? EG X] 4n 1= 16n2 T VarG X 0 p 1 (7)= 16n2 T O( n ): Inequality (4) is from Jensen's inequality and concavity of square root 8, eq. V.8.6]; (5) holds because= EX minimizes E(X? )2; (6) because the absolute value of the gradient of A is bounded by 1=4T; and (7) follows by regarding X 0 as a sum and di erence of Bernoulli r.v.s (see eq. (2)). It follows that q q q
EG kP? P k= b
X 0
EG jP (; 0)? P (; 0)j b
6= pn=T ):= O( 0
2
X
EG jP (; 0)? P (; 0)j b
(8)
Next we claim that for any, and any c> 0, Pr kP (; )? P (; )k? EG kP (; )? P (; )k G b b b
cpn T
!
2 exp(?c2n):
(9)
As usual this follows from applying the method of bounded di erences, in this case to kP (; )? P (; )k, viewed as a function of G. Changing any edge indicator variable (u; v) does not a ect any P (; ). It changes P (; 0) for only 4n states 0, and then| 1 for 0 6=| by at most 4n2 41T: the probability of generating the state times the maximum possible change in the probability of accepting it. It therefore changes P (; ) by at 1 most the same total amount 4nT . So each (u; v) causes a change to kP (; )? P (; )k of c(u; v) 1=2nT, resulting in c(u; v)2 2T?2, whence (9) follows by Azuma's inequality. Combining equations (8) and (9), for any, b b P
Pr kP (; )? P (; )k O T G b
pn
!
c n+ T
p
!
2 exp(?c2n):
The probability over G 2 G4n;p;r that there is any rough is at most the expected number of 's which are rough, and since there are exactly (4n) possible values of, this 2n is exp (O(4n)? c2n)= exp (? (n)) for c su ciently large. That is, all but a fraction ex
p(? (n)) of graphs G 2 G4n;p;r have no rough partitions. 10
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...
热门文档