OPTIMIZATION

There is nowadays a growing interest in computational models inspired in physical and natural phenomena (quantum computing, DNA computing, evolutionary algorithms, chaotic networks). This, together with the practical successes attained by artificial neural networks, has raised some intriguing theoretical questions on the links between discrete and analog computation. Is there a relationship between the complexity of algorithms in the continuous and discrete settings for solving the same problem? How do approximate solutions affect the complexity?

Computational complexity theory, as developed within Computer Science, has focused on discrete computation, whereas analog computation has mainly been studied using the tools of Theoretical Physics. However, to try to answer the above questions, theories to study both types of computation under a unifying perspective are needed, and these are only beginning to be developed.

Combinatorial optimization

Guimerà, Sales-Pardo, Amaral, Modularity from fluctuations in random graphs and complex networks, Physical Review E 70, 025101 (2004).

Bofill, Guimerà, Torras, Comparison of simulated annealing and mean field annealing as applied to the generation of balanced incomplete block designs, Neural Networks 16, 1421-1428 (2003).

Optimal networks

Guimerà, Arenas, Díaz-Guilera, Vega-Redondo, Cabrales, Optimal network topologies for local search with congestion, Physical Review Letters 89, 248701 (2002).

Arenas, Cabrales, Díaz-Guilera, Guimerà, Vega-Redondo, Search and congestion in complex networks, in Statistical Mechanics of Complex Networks (ed. Pastor-Satorras, Rubí, Díaz-Guilera) (2003).