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
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...
热门文档