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

Simulated Annealing for Graph Bisection

Simulated Annealing for Graph Bisection

Simulated Annealing for Graph Bisection Mark Jerrum Gregory Sorkin y April 16, 1993

We resolve in the a rmative a question of Boppana and Bui: whether simulated annealing can, with high probability and in polynomial time, nd the optimal bisection of a random graph in Gnpr when p? r= (n?2 ) for 2. (The random graph model Gnpr speci es a\planted" bisection of density r, separating two n=2vertex subsets of slightly higher density p.) We show that simulated\annealing" at an appropriate xed temperature (i.e., the Metropolis algorithm) nds the unique smallest bisection in O(n2+" ) steps with very high probability, provided> 11=6. (By using a slightly modi ed neighborhood structure, the number of steps can be reduced to O(n1+" ).) We leave open the question of whether annealing is e ective for in the range 3=2< 11=6, whose lower limit represents the threshold at which the planted bisection becomes lost amongst other random small bisections. It remains open whether hillclimbing (i.e., annealing at temperature 0) solves the same problem.

Abstract

1 Introduction Simulated annealing 15] is a popular heuristic technique for approximately solving hard problems in combinatorial optimization. The method works by simulating a stochastic process on the space of feasible solutions, in which transitions between states are governed by a rule that favors states with lower cost or\energy". A parameter known as\temperature" controls the extent to which lower energy states are favored: at low temperature equilibrium, low energy states occur with much higher probability than high energy ones, while at high temperatures the di erence is less marked. To this extent, a low temperature is bene cial; however there is a tension between this e ect and a detrimental one, Department of Computer Science, University of Edinburgh, The King's Buildings, Edinburgh EH9 3JZ, UK. The work described here was supported by grant GR/F 90363 of the UK Science and Engineering Research Council and by Esprit Working Group\RAND", and was partly done while the author was visiting the NEC Research Institute at Princeton NJ, USA. y IBM Thomas J. Watson Research Center, J2-C27 Hawthorne, PO Box 704, Yorktown Heights, NY 10598, USA. This work was partly done while the author was visiting the University of Edinburgh under the above SERC grant.

第1页

你可能喜欢

热门文档

相关文档

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