Bibliographic record and links to related information available from the Library of Congress catalog
Note: Electronic data is machine generated. May be incomplete or contain other coding.
1 Introduction 1 1.1 From A Priori to Online Stochastic Optimization 1 1.2 Online Stochastic Combinatorial Optimization 2 1.3 Online Anticipatory Algorithms 4 1.4 Online Stochastic Combinatorial Optimization in Context 5 1.5 Organization and Themes 13 I ONLINE STOCHASTIC SCHEDULING 2 Online Stochastic Scheduling 19 2.1 The Generic Offline Problem 19 2.2 The Online Problem 20 2.3 The Generic Online Algorithm 20 2.4 Properties of Online Stochastic Scheduling 22 2.5 Oblivious Algorithms 23 2.6 The Expectation Algorithm 24 2.7 The Consensus Algorithm 26 2.8 The Regret Algorithm 27 2.9 Immediate Decision Making 30 2.10 The Suboptimality Approximation Problem 31 2.11 Notes and Further Reading 33 3 Theoretical Analysis 35 3.1 Expected Loss 35 3.2 Local Errors 36 3.3 Bounding Local Errors 38 3.4 The Theoretical Results 40 3.5 Discussion on the Theoretical Assumptions 41 3.6 Notes and Further Reading 43 4 Packet Scheduling 45 4.1 The Packet Scheduling Problem 45 4.2 The Optimization Algorithm 46 4.3 The Greedy Algorithm is Competitive 50 4.4 The Suboptimality Approximation 51 4.5 Experimental Setting 53 4.6 Experimental Results 54 4.7 The Anticipativity Assumption 60 4.8 Notes and Further Reading 66 II ONLINE STOCHASTIC RESERVATIONS 5 Online Stochastic Reservations 71 5.1 The Offline Reservation Problem 71 5.2 The Online Problem 72 5.3 The Generic Online Algorithm 73 5.4 The Expectation Algorithm 74 5.5 The Consensus Algorithm 74 5.6 The Regret Algorithm 75 5.7 Cancellations 77 6 Online Multiknapsack Problems 79 6.1 Online Multiknapsack with Deadlines 79 6.2 The Suboptimality Approximation 81 6.3 Experimental Results 89 6.4 Notes and Further Reading 98 III ONLINE STOCHASTIC ROUTING 7 Vehicle Routing with Time Windows 103 7.1 Vehicle Dispatching and Routing 103 7.2 Large Neighborhood Search 107 7.3 Notes and Further Reading 112 8 Online Stochastic Routing 113 8.1 Online Stochastic Vehicle Routing 113 8.2 Online Single Vehicle Routing 116 8.3 Service Guarantees 118 8.4 A Waiting Strategy 120 8.5 A Relocation Strategy 121 8.6 Multiple Pointwise Decisions 122 8.7 Notes and Further Reading 125 9 Online Vehicle Dispatching 127 9.1 The Online Vehicle Dispatching Problems 127 9.2 Setting of the Algorithms 128 9.3 Experimental Results 129 9.4 Visualizations of the Algorithms 138 9.5 Notes and Further Reading 149 10 Online Vehicle Routing with Time Windows 153 10.1 The Online Instances 153 10.2 Experimental Setting 155 10.3 Experimental Results 156 10.4 Notes and Further Reading 165 IV LEARNING AND HISTORICAL SAMPLING 11 Learning Distributions 171 11.1 The Learning Framework 171 11.2 Hidden Markov Models 172 11.3 Learning Hidden Markov Models 174 11.4 Notes and Further Reading 182 12 Historical Sampling 185 12.1 Historical Averaging 185 12.2 Historical Sampling 186 V SEQUENTIAL DECISION MAKING 13 Markov Chance-Decision Processes 193 13.1 Motivation 193 13.2 Decision-Chance versus Chance-Decision 194 13.3 Equivalence of MDCPs and MCDPs 196 13.4 Online Anticipatory Algorithms 199 13.5 The Approximation Theorem for Anticipative MCDPs 202 13.6 The Anticipativity Assumption 208 13.7 Beyond Anticipativity 210 13.8 The General Approximation Theorem for MCDPs 214 13.9 Notes and Further Reading 218