Stochastic Algorithms: Foundations and Applications

1. Front Matter

   PDF

2. Invited Papers

   1. Scenario Reduction Techniques in Stochastic Programming

      • Werner Römisch

      Pages 1-14

   2. Statistical Learning of Probabilistic BDDs

      • Taisuke Sato

      Pages 15-15

3. Regular Contributions

   1. Learning

      1. Learning Volatility of Discrete Time Series Using Prediction with Expert Advice

         • Vladimir V. V’yugin

         Pages 16-30

      2. Prediction of Long-Range Dependent Time Series Data with Performance Guarantee

         • Mikhail Dashevskiy, Zhiyuan Luo

         Pages 31-45

      3. Bipartite Graph Representation of Multiple Decision Table Classifiers

         • Kazuya Haraguchi, Seok-Hee Hong, Hiroshi Nagamochi

         Pages 46-60

      4. Bounds for Multistage Stochastic Programs Using Supervised Learning Strategies

         • Boris Defourny, Damien Ernst, Louis Wehenkel

         Pages 61-73

      5. On Evolvability: The Swapping Algorithm, Product Distributions, and Covariance

         • Dimitrios I. Diochnos, György Turán

         Pages 74-88

   2. Graphs

      1. A Generic Algorithm for Approximately Solving Stochastic Graph Optimization Problems

         • Ei Ando, Hirotaka Ono, Masafumi Yamashita

         Pages 89-103

      2. How to Design a Linear Cover Time Random Walk on a Finite Graph

         • Yoshiaki Nonaka, Hirotaka Ono, Kunihiko Sadakane, Masafumi Yamashita

         Pages 104-116

      3. Propagation Connectivity of Random Hypergraphs

         • Robert Berke, Mikael Onsjö

         Pages 117-126

      4. Graph Embedding through Random Walk for Shortest Paths Problems

         • Yakir Berchenko, Mina Teicher

         Pages 127-140

   3. Testing, Optimization, and Caching

      1. Relational Properties Expressible with One Universal Quantifier Are Testable

         • Charles Jordan, Thomas Zeugmann

         Pages 141-155

      2. Theoretical Analysis of Local Search in Software Testing

         • Andrea Arcuri

         Pages 156-168

      3. Firefly Algorithms for Multimodal Optimization

         • Xin-She Yang

         Pages 169-178

      4. Economical Caching with Stochastic Prices

         • Matthias Englert, Berthold Vöcking, Melanie Winkler

         Pages 179-190

   4. Stochastic Algorithms in Bioinformatics

      1. Markov Modelling of Mitochondrial BAK Activation Kinetics during Apoptosis

         • C. Grills, D. A. Fennell, S. F. C. Shearer

         Pages 191-205

      2. Stochastic Dynamics of Logistic Tumor Growth

         • S. F. C. Shearer, S. Sahoo, A. Sahoo

         Pages 206-220

4. Back Matter

   PDF

This book constitutes the refereed proceedings of the 5th International Symposium on Stochastic Algorithms, Foundations and Applications, SAGA 2009, held in Sapporo, Japan, in October 2009. The 15 revised full papers presented together with 2 invited papers were carefully reviewed and selected from 22 submissions. The papers are organized in topical sections on learning, graphs, testing, optimization and caching, as well as stochastic algorithms in bioinformatics.

• Graph
• algorithms
• approximation
• bioinformatics
• complexity
• counting algorithm
• dynamical-probability
• evolution
• evolutionary algorithms
• genetic algorithms
• graph embedding
• learning
• normal distribution
• optimization
• randomization
• data structures
• algorithm analysis and problem complexity

• Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, W8-25, Tokyo, Japan

  Osamu Watanabe

• Division of Computer Science, N-14, W-9, Hokkaido University, Sapporo, Japan

  Thomas Zeugmann

Policies and ethics