Extremal Optimization

Publications

• G. Istrate, S. Boettcher and A.G. Percus, Spines of random constraint satisfaction problems: definition and connection with computational complexity, Annals of Mathematics and Artificial Intelligence 44, 353-372 (2005).

• S. Boettcher and A.G. Percus, Extremal optimization at the phase transition of the 3-coloring problem, Physical Review E 69, 066703 (2004). Copyright © 2004 by American Physical Society.

• S. Boettcher, G. Istrate and A.G. Percus, Spines of random constraint satisfaction problems: definition and impact on computational complexity, Proceedings of the 8th International Symposium on Artificial Intelligence and Mathematics (AIMATH '04), AI&M 2-2004.

• S. Boettcher and A.G. Percus, Extremal optimization: an evolutionary local-search algorithm in: H.K. Bhargava and N. Ye, eds., Computational Modeling and Problem Solving in the Networked World: Interfaces in Computer Science and Operations Research (Kluwer Academic Publishers, Dordrecht, Netherlands, 2003), pp. 61-77.

• S. Boettcher and A.G. Percus, Optimization with extremal dynamics, Complexity 8, 57-62 (2003).

• S. Boettcher and M. Grigni, Jamming model for the extremal optimization heuristic, Journal of Physics A: Math. Gen. 35, 1109-1123 (2002).

• S. Boettcher and A.G. Percus, Extremal optimization for graph partitioning, Physical Review E 64, 026114 (2001). Copyright © 2001 by American Physical Society.

• S. Boettcher and A.G. Percus, Optimization with extremal dynamics, Physical Review Letters 86, 5211-5214 (2001). Copyright © 2001 by American Physical Society.

• D. Achlioptas, A. Chtcherba, G. Istrate, and C. Moore, The phase transition in 1-in-k SAT and NAE 3-SAT, Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '01), 719-720 (2001).

• S. Boettcher and A.G. Percus, Nature's way of optimizing, Artificial Intelligence 119, 275-286 (2000). Copyright © 2000 by Elsevier Science.

• S. Boettcher, Extremal optimization: heuristics via co-evolutionary avalanches, Computing in Science and Engineering 2:6, 75-82 (2000). Copyright © 2000 by IEEE.

• S. Boettcher, A.G. Percus, and M. Grigni, Optimizing through co-evolutionary avalanches, Proceedings of the Sixth International Conference on Parallel Problem Solving from Nature. Lecture Notes in Computer Science 1917, 447-456 (2000).

• S. Boettcher and A.G. Percus, Combining local search with co-evolution in a remarkably simple way, Proceedings of the 2000 Congress on Evolutionary Computation, 1578-1584 (2000). Copyright © 2000 by the IEEE.

• G. Istrate, Computational complexity and phase transitions, Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 104-115 (2000).

• S. Boettcher and A.G. Percus, Extremal optimization: Methods derived from co-evolution, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '99), 825-832 (1999).

• S. Boettcher, Extremal optimization of graph partitioning at the percolation threshold, Journal of Physics A 32, 5201-5211 (1999).

• S. Boettcher, Optimizing partitions of percolating graphs, Physica A 266, 100-103 (1999).

Related links

• Workshop on Computational Complexity and Statistical Physics, 4-6 September 2001, Santa Fe.

• Gabi Istrate's lecture series on Markov Chain Techniques in Theoretical Computer Science.

Last modified: 18 November 2005