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.
Author(s): Osamu Watanabe, Thomas Zeugmann
Series: Lecture Notes in Computer Science - Theoretical Computer Science and General Issues
Publisher: Springer
Year: 2010
Language: English
Pages: 229
front-matter......Page 1
Introduction......Page 9
Stability and Distances of Probability Distributions......Page 11
Optimal Scenario Reduction......Page 14
Two-Stage Stochastic Linear Programs......Page 15
Two-Stage Stochastic Mixed-Integer Programs......Page 16
Statistical Learning of Probabilistic BDDs......Page 23
Introduction......Page 24
Arbitrage Strategies......Page 26
The Follow Perturbed Leader Algorithm with Adaptive Weights......Page 28
Zero-Sum Game......Page 36
Conclusion......Page 37
Introduction......Page 39
Fractional Auto-Regressive Integrated Moving Average (FARIMA)......Page 40
Prediction for ARMA Processes......Page 42
Innovations Algorithm......Page 43
Kalman Filter......Page 45
Aggregating Algorithm......Page 46
Experiments and Results......Page 48
Conclusions......Page 52
Classification Problem......Page 54
Background on Visual Classifier......Page 55
New Contribution......Page 57
Decision Table......Page 59
Sample-Entry Graph (SE-Graph)......Page 60
Poset and Crossing Minimization on SE-Graph......Page 62
Construction Algorithm of SE-Graph Classifier......Page 63
Experimental Results......Page 65
Concluding Remarks......Page 66
Context......Page 69
Motivation......Page 71
Datasets......Page 72
Generalization Strategies......Page 73
Learning Algorithms......Page 76
Related Work......Page 78
Conclusion......Page 79
Introduction......Page 82
An Informal Description of the Swapping Algorithm......Page 84
Preliminaries......Page 85
Properties of the Local Search Procedure......Page 86
Evolving Monotone Conjunctions under the Uniform Distribution......Page 87
Monotone Conjunctions under Product Distributions Using Correlation......Page 90
Properties of the Local Search Procedure......Page 91
Covariance as a Fitness Function......Page 92
Evolving Short Monotone Conjunctions under -Nondegenerate Product Distributions......Page 94
Further Remarks......Page 95
Motivation and Contribution......Page 97
Related Works......Page 100
Preliminaries......Page 101
A Lower Bound on $F_{\rm MAX}(x)$......Page 102
Constructing $\tilde F(x)$......Page 103
Efficient Evaluation of $\tilde F^{-1}(a)$......Page 104
Bounding Approximation Ratio......Page 105
Discussions and Conclusions......Page 107
Handling Minimization Problems......Page 108
Using $A_{\rm APR}$ Instead of $A_{\rm MAX}$......Page 109
Handling Other Distributions......Page 110
Random Walks......Page 112
Related Work......Page 113
Preliminaries......Page 114
Lower Bound on the Cover Time for a Star Graph......Page 115
Lower Bound of the Cover Time on Tree......Page 117
Biconnected Component Decomposition......Page 119
Sufficient Condition of Linear Cover Time Random Walk......Page 120
Hamiltonian Component Decomposition......Page 121
Conclusion......Page 123
Introduction......Page 125
Preliminaries: Problem and Algorithm......Page 126
Propagation Connectivity......Page 129
Some Notes......Page 133
Introduction......Page 135
Definitions and Notations......Page 137
The Embedding Procedure......Page 138
Routing......Page 139
Distance Estimation......Page 141
Non-sparse Random Graphs......Page 143
The PGP Network......Page 144
Conclusions and Discussion......Page 147
Introduction......Page 149
Preliminaries......Page 150
Property Testing Definitions......Page 151
Logical Definitions......Page 152
Variations of Relational Property Testing......Page 153
Classification Similarities......Page 157
Ackermann's Class with Equality......Page 158
Conclusion......Page 162
Introduction......Page 164
Runtime Analysis......Page 165
Search Based Software Testing......Page 166
Class of Software......Page 167
Search Algorithms......Page 168
Theoretical Runtime Analysis......Page 169
Empirical Analysis......Page 172
Discussion......Page 173
Conclusion......Page 174
Introduction......Page 177
Behaviour of Fireflies......Page 178
Firefly Algorithm......Page 179
Attractiveness......Page 180
Distance and Movement......Page 181
Scaling and Asymptotic Cases......Page 182
Validation......Page 183
Comparison of FA with PSO and GA......Page 184
Conclusions......Page 186
Introduction......Page 187
Formal Description of the Problem......Page 188
Preliminaries......Page 189
Our Results......Page 190
Cautious Is the Optimal Online Algorithm......Page 191
Expected Cost of Cautious......Page 192
Expected Savings of Cautious......Page 194
Expected Savings of the Optimal Offline Algorithm......Page 195
Conclusions......Page 197
Introduction......Page 199
Theoretical Calculations......Page 201
System 1: Agonist Driven BAK Activation......Page 202
System 2: Derepressor Model of BAK Activation......Page 204
System 3: The Unified Model......Page 206
Agonist Only BAK Activation......Page 208
Combined Agonist and Derepressor Model......Page 209
Conclusions......Page 211
Introduction......Page 214
The Model......Page 215
Eigenvalue Problem for the Fokker-Planck Equation......Page 217
B-Spline Implementation......Page 219
Calculating Eigenfunctions and Eigenvalues of the Sturm-Liouville Equation Using B-Splines......Page 220
Eigenfunctions of the Sturm-Liouville Equation......Page 221
Results and Discussion......Page 222
Effect of Uncorrelated Noise......Page 224
Summary and Conclusions......Page 227
back-matter......Page 229
