دانلود کتاب Online Stochastic Combinatorial Optimization

فهرست مطالب :

Contents......Page 3
Preface......Page 7
From A Priori to Online Stochastic Optimization......Page 11
Online Stochastic Combinatorial Optimization......Page 12
Online Anticipatory Algorithms......Page 14
Online Stochastic Combinatorial Optimization in Context......Page 15
Organization and Themes......Page 23
--- Sequencial Decision Making......Page 0
The Generic Offline Problem......Page 26
The Generic Online Algorithm......Page 27
Properties of Online Stochastic Scheduling......Page 29
Oblivious Algorithms......Page 30
The Expectation Algorithm......Page 31
The Consensus Algorithm......Page 33
The Regret Algorithm......Page 34
Immediate Decision Making......Page 37
The Suboptimality Approximation Problem......Page 38
Notes and Further Reading......Page 40
Expected Loss......Page 41
Local Errors......Page 42
Bounding Local Errors......Page 44
The Theoretical Results......Page 46
Discussion on the Theoretical Assumptions......Page 47
Notes and Further Reading......Page 49
The Packet Scheduling Problem......Page 50
The Optimization Algorithm......Page 51
The Greedy Algorithm is Competitive......Page 55
The Suboptimality Approximation......Page 56
Experimental Setting......Page 58
Experimental Results......Page 59
The Anticipativity Assumption......Page 65
Notes and Further Reading......Page 71
The Offline Reservation Problem......Page 73
The Online Problem......Page 74
The Generic Online Algorithm......Page 75
The Consensus Algorithm......Page 76
The Regret Algorithm......Page 77
Cancellations......Page 79
Online Multiknapsack with Deadlines......Page 80
The Suboptimality Approximation......Page 82
Experimental Results......Page 90
Notes and Further Reading......Page 99
Vehicle Dispatching and Routing......Page 101
Large Neighborhood Search......Page 105
Notes and Further Reading......Page 110
Online Stochastic Vehicle Routing......Page 111
Online Single Vehicle Routing......Page 114
Service Guarantees......Page 116
A Waiting Strategy......Page 118
A Relocation Strategy......Page 119
Multiple Pointwise Decisions......Page 120
Notes and Further Reading......Page 123
The Online Vehicle Dispatching Problems......Page 124
Setting of the Algorithms......Page 125
Experimental Results......Page 126
Visualizations of the Algorithms......Page 135
Notes and Further Reading......Page 146
The Online Instances......Page 150
Experimental Setting......Page 152
Experimental Results......Page 153
Notes and Further Reading......Page 162
The Learning Framework......Page 166
Hidden Markov Models......Page 167
Learning Hidden Markov Models......Page 169
Notes and Further Reading......Page 177
Historical Averaging......Page 179
Historical Sampling......Page 180
Motivation......Page 185
Decision-Chance versus Chance-Decision......Page 186
Equivalence of MDCPs and MCDPs......Page 188
Online Anticipatory Algorithms......Page 191
The Approximation Theorem for Anticipative MCDPs......Page 194
The Anticipativity Assumption......Page 200
Beyond Anticipativity......Page 202
The General Approximation Theorem for MCDPs......Page 206
Notes and Further Reading......Page 210
Refs......Page 211
Index......Page 220