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

Simulated Annealing for Graph Bisection

Simulated Annealing for Graph Bisection

where we have used the fact that X 0? X+ is non-negative. (Naturally, the expectations here are with respect to the sample space constructed earlier.) The result follows immediately. For a given partition with imbalance k, let f+= f+(G; ) be a random variable denoting the probability that the new partition after one move has imbalance k+ 1. Let f?= f? (G; ) be the corresponding r.v. for k-decreasing moves.

Corollary 3.3 Suppose T pn. Then for a partition with imbalance k, 1 EG f+ (G; ) 8+ (minfk (p? r)=T; 1g)? O(k=n) and

EG f? (G; )

1 8?

(minfk(p? r)=T; 1g)+ O(k

=n)

where the expectation is over random graphs G 2 G4n;p;r .

Proof Follows from+Claim 3.1, Claim 3.2, and symmetry.

To show that f is concentrated near its expected value we employ a\bounded di erence" inequality. Speci cally we use a generalization of Azuma's inequality in a form due to McDiarmid 16] (see also Bollobas 2]): Theorem 3.4 (Azuma) Let X1;:::; Xn be independent random variables, with Xk taking values in a set Ak for each k. Suppose that the (measurable) function f: Ak ! R satis es jf (x)? f (x0 )j ck whenever the vectors x and x0 di er only in the k'th coordinate. Let Y be the random variable f (X1;:::; Xn ). Then for any t> 0, Pr jY? EY j t] 2 exp(?2t2= c2 ). k Q P

De nition 3.5 Call a pair (G; ) -atypical if either jf+ (G; )? EG f+ (G; )j> or jf?(G; )? EG f? (G; )j> . Claim 3.6 (atypicality) For any partition and any> 0, the probability, over random G 2 G4n;p;r, that (G; ) is -atypical is at most 4 exp(?4 2 T 2).

the edges, f+(G; ) is a function of these independent r.v.s: it is the sum over k-increasing moves (i; j ) that the move is both proposed and accepted. Varying one (u; v) while leaving all other 's xed, the probability of proposing a particular move (i; j ) taking k to k+ 1 is unchanged at 1=(2n)2 . The probability of accepting (i; j ) changes only for the 4n values of i; j for which fi; j g\fu; vg 6=;. Even then the move's cost change X is altered by at most 1, and the derivative of the acceptance function A is bounded in absolute value by 1=4T, so the acceptance probability A(X ) changes by at most 1=4T . Thus changing a single (u; v) changes f+ by at most 1 1 c(u; v)= (2n)2 4n 41T= 4nT; summing over all (42n) pairs fu; vg gives c(u; v)2 1=2T 2, whereupon Azuma's inequality yields the claim. P

Proof Equating G with the collection f (u; v): fu; vg 2 V (2)g of indicator variables for

上一页第7页

你可能喜欢

热门文档

相关文档

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