Stochastic Algorithms: Foundations and Applications

This book constitutes the refereed proceedings of the Second International Symposium on Stochastic Algorithms: Foundations and Applications, SAGA 2003, held in Hatfield, UK in September 2003.The 12 revised full papers presented together with three invited papers were carefully reviewed and selected for inclusion in the book. Among the topics addressed are ant colony optimization, randomized algorithms for the intersection problem, local search for constraint satisfaction problems, randomized local search and combinatorial optimization, simulated annealing, probabilistic global search, network communication complexity, open shop scheduling, aircraft routing, traffic control, randomized straight-line programs, and stochastic automata and probabilistic transformations.

Prospects of Quantum Informatics.- A Converging ACO Algorithm for Stochastic Combinatorial Optimization.- Optimality of Randomized Algorithms for the Intersection Problem.- Stochastic Algorithms for Gene Expression Analysis.- Analysis of a Randomized Local Search Algorithm for LDPCC Decoding Problem.- Testing a Simulated Annealing Algorithm in a Classification Problem.- Global Search through Sampling Using a PDF.- Simulated Annealing for Optimal Pivot Selection in Jacobian Accumulation.- Quantum Data Compression.- Who'sThe Weakest Link?.- On the Stochastic Open Shop Problem.- Global Optimization - Stochastic or Deterministic?.- Two-Component Traffic Modelled by Cellular Automata: Imposing Passing Restrictions on Slow Vehicles Increases the Flow.- Average-Case Complexity of Partial Boolean Functions.- Classes of Binary Rational Distributions Closed under Discrete Transformations.