| Автор | Stefan Boettcher |
| Дата выпуска | 1999-07-16 |
| dc.description | The benefits of a recently proposed method to approximate hard optimization problems are demonstrated on the graph partitioning problem. The performance of this new method, called extremal optimization (EO), is compared with simulated annealing (SA) in extensive numerical simulations. While generally a complex (NP-hard) problem, the optimization of the graph partitions is particularly difficult for sparse graphs with average connectivities near the percolation threshold. At this threshold, the relative error of SA for large graphs is found to diverge relative to EO at equalized runtime. On the other hand, EO, based on the extremal dynamics of self-organized critical systems, reproduces known results about optimal partitions at this critical point quite well. |
| Формат | application.pdf |
| Издатель | Institute of Physics Publishing |
| Название | Extremal optimization of graph partitioning at the percolation threshold |
| Тип | paper |
| DOI | 10.1088/0305-4470/32/28/302 |
| Print ISSN | 0305-4470 |
| Журнал | Journal of Physics A: Mathematical and General |
| Том | 32 |
| Первая страница | 5201 |
| Последняя страница | 5211 |
| Аффилиация | Stefan Boettcher; Physics Department, Emory University, Atlanta, GA 30322, USA; Center for Nonlinear Studies, Los Alamos National Laboratory, Los Alamos, NM 87545, USA |
| Выпуск | 28 |
