The Design of Competitive Online Algorithms via a Primal-Dual Approach
Seiten
2009
now publishers Inc (Verlag)
978-1-60198-216-2 (ISBN)
now publishers Inc (Verlag)
978-1-60198-216-2 (ISBN)
Extends the primal-dual method to the setting of online algorithms, and shows its applicability to a wide variety of fundamental problems. Among the online problems considered are the weighted caching problem, generalized caching, the set-cover problem, graph optimization problems, routing, load balancing, and the problem of allocating ad-auctions.
This book extends the primal-dual method to the setting of online algorithms, and shows its applicability to a wide variety of fundamental problems. Among the online problems considered are the weighted caching problem, generalized caching, the set-cover problem, several graph optimization problems, routing, load balancing, and the problem of allocating ad-auctions. There is also an illustration of how classic online problems such as the ski rental problem and the dynamic TCP-acknowledgement problem can be solved optimally using a simple primal-dual approach.
The Design of Competitive Online Algorithms Via a Primal-Dual Approach is an invaluable reference for anyone working in the area of computational theory, and especially those interested in exploring online scenarios that can benefit from the primal-dual framework.
This book extends the primal-dual method to the setting of online algorithms, and shows its applicability to a wide variety of fundamental problems. Among the online problems considered are the weighted caching problem, generalized caching, the set-cover problem, several graph optimization problems, routing, load balancing, and the problem of allocating ad-auctions. There is also an illustration of how classic online problems such as the ski rental problem and the dynamic TCP-acknowledgement problem can be solved optimally using a simple primal-dual approach.
The Design of Competitive Online Algorithms Via a Primal-Dual Approach is an invaluable reference for anyone working in the area of computational theory, and especially those interested in exploring online scenarios that can benefit from the primal-dual framework.
1: Preface. 2: Necessary Background. 3: A First Glimpse: The Ski Rental Problem. 4: The Basic Approach. 5: The Online Set Cover Problem. 6: The Metrical Task System Problem on a Weighted Star. 7: Generalized Caching. 8: Load Balancing on Unrelated Machines. 9: Routing. 10: Maximizing Ad-auctions revenue. 11: Graph Optimization Problems. 12: Dynamic TCP-Acknowledgement Problem. 13: The Bounded Allocation Problem: Beating (1 - 1/e). 14: Extension to General Packing-Covering Constraints. 15: Conclusions and Further Research. References
| Erscheint lt. Verlag | 15.5.2009 |
|---|---|
| Reihe/Serie | Foundations and Trends® in Theoretical Computer Science |
| Verlagsort | Hanover |
| Sprache | englisch |
| Maße | 156 x 234 mm |
| Gewicht | 278 g |
| Themenwelt | Informatik ► Theorie / Studium ► Algorithmen |
| ISBN-10 | 1-60198-216-X / 160198216X |
| ISBN-13 | 978-1-60198-216-2 / 9781601982162 |
| Zustand | Neuware |
| Informationen gemäß Produktsicherheitsverordnung (GPSR) | |
| Haben Sie eine Frage zum Produkt? |
Mehr entdecken
aus dem Bereich
aus dem Bereich
Buch | Softcover (2024)
Lehmanns Media (Verlag)
CHF 55,95
how metrics are transforming the work of journalists
Buch | Softcover (2024)
Princeton University Press (Verlag)
CHF 33,15
Eine Einführung mit Java
Buch | Hardcover (2020)
dpunkt (Verlag)
CHF 62,85
