The DOI matches its Crossref record; 22 of the 22 references it cites were found in a registry or an index.
Optimization with Extremal Dynamics
Open accessAbstract
We explore a new general-purpose heuristic for finding high-quality solutions to hard discrete optimization problems. The method, called extremal optimization, is inspired by self-organized criticality, a concept introduced to describe emergent complexity in physical systems. Extremal optimization successively updates extremely undesirable variables of a single suboptimal solution, assigning them new, random values. Large fluctuations ensue, efficiently exploring many local optima. We use extremal optimization to elucidate the phase transition in the 3-coloring problem, and we provide independent confirmation of previously reported extrapolations for the ground-state energy of +/-J spin glasses in d = 3 and 4.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Holland, J. H. (1992) · The MIT Press eBooks · doi:10.7551/mitpress/1090.001.0001 · Cited by 47,002
Optimization by Simulated Annealing
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983) · Science · doi:10.1126/science.220.4598.671 · Cited by 45,134
(1979) · Cited by 43,841
Self-organized criticality: An explanation of the 1/f noise
Bak, P., Tang, C., & Wiesenfeld, K. (1987) · Physical Review Letters · doi:10.1103/physrevlett.59.381 · Cited by 7,591
Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications
Mezard, M., Parisi, G., & Virasoro, M. (1986) · World Scientific Lecture Notes in Physics · doi:10.1142/0271 · Cited by 3,653
Bak, P. (1996) · Springer eBooks · doi:10.1007/978-1-4757-5426-1 · Cited by 2,809
Punctuated equilibrium and criticality in a simple model of evolution
Bak, P., & Sneppen, K. (1993) · Physical Review Letters · doi:10.1103/physrevlett.71.4083 · Cited by 1,497
On the computational complexity of Ising spin glass models
Barahona, F. (1982) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/15/10/028 · Cited by 1,306
Where the really hard problems are
Cheeseman, P. C., Kanefsky, B., & Taylor, W. M. (1991) · Cited by 1,004
Determining computational complexity from characteristic ‘phase transitions’
Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., & Troyansky, L. (1999) · Nature · doi:10.1038/22055 · Cited by 790
Critical Behavior in the Satisfiability of Random Boolean Expressions
Kirkpatrick, S., & Selman, B. (1994) · Science · doi:10.1126/science.264.5163.1297 · Cited by 589
Avalanche dynamics in evolution, growth, and depinning models
Paczuski, M., Maslov, S., & Bak, P. (1996) · Physical Review E · doi:10.1103/physreve.53.414 · Cited by 577
Boettcher, S., & Percus, A. (2000) · Artificial Intelligence · doi:10.1016/s0004-3702(00)00007-2 · Cited by 278
Self-citationExtremal optimization for graph partitioning
Boettcher, S., & Percus, A. G. (2001) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.64.026114 · Cited by 138
Self-citationThe ground state energy of the Edwards-Anderson Ising spin glass with a hybrid genetic algorithm
Pál, K. F. (1996) · Physica A Statistical Mechanics and its Applications · doi:10.1016/0378-4371(95)00348-7 · Cited by 80
Extremal optimization: heuristics via coevolutionary avalanches
Boettcher, S. (2000) · Computing in Science & Engineering · doi:10.1109/5992.881710 · Cited by 62
Self-citationExtremal optimization of graph partitioning at the percolation threshold
Boettcher, S. (1999) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/32/28/302 · Cited by 55
Self-citationRenormalization for Discrete Optimization
Houdayer, J., & Martin, O. (1999) · Physical Review Letters · doi:10.1103/physrevlett.83.1030 · Cited by 45
Evidence for nontrivial ground-state structure of 3d ± J spin glasses
Hartmann, A. K. (1997) · Europhysics Letters (EPL) · doi:10.1209/epl/i1997-00483-y · Cited by 41
Optimization on Rugged Landscapes: A New General Purpose Monte Carlo Approach
Dittes, F.-M. (1996) · Physical Review Letters · doi:10.1103/physrevlett.76.4651 · Cited by 37
Ultrametricity and memory in a solvable model of self-organized criticality
Boettcher, S., & Paczuski, M. (1996) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.54.1082 · Cited by 31
Self-citationOptimizing through Co-evolutionary Avalanches
Boettcher, S., Percus, A. G., & Grigni, M. (2000) · Lecture notes in computer science · doi:10.1007/3-540-45356-3_44 · Cited by 15
Self-citation
Cited by
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
Comparing community structure identification
Danon, L., Díaz-Guilera, A., Duch, J., & Arenas, A. (2005) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2005/09/p09008 · Cited by 2,872
Community detection in complex networks using extremal optimization
Duch, J., & Arenas, A. (2005) · Physical Review E · doi:10.1103/physreve.72.027104 · Cited by 1,549
Influence maximization in complex networks through optimal percolation
Morone, F., & Makse, H. A. (2015) · Nature · doi:10.1038/nature14604 · Cited by 1,230
Vital nodes identification in complex networks
Lü, L., Chen, D., Ren, X.-L., Zhang, Q.-M., Zhang, Y.-C., & Zhou, T. (2016) · Physics Reports · doi:10.1016/j.physrep.2016.06.007 · Cited by 1,183
Metadata
- Authors
- Boettcher, S., & Percus, A. G.
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2001-06-04
- Volume
- 86
- Issue
- 23
- Pages
- 5211-5214
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W2963332217
- Cited by
- 342
- References
- 22
- FWCI
- 7.98
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.