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

Simulated Annealing for Graph Bisection

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

上一页第10页

你可能喜欢

热门文档

相关文档

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