Buch, Englisch, Band 10, 176 Seiten, Format (B × H): 156 mm x 234 mm
Reihe: Foundations and Trends® in Theoretical Computer Science
Buch, Englisch, Band 10, 176 Seiten, Format (B × H): 156 mm x 234 mm
Reihe: Foundations and Trends® in Theoretical Computer Science
ISBN: 978-1-60198-216-2
Verlag: Now Publishers
The Design of Competitive Online Algorithms via a Primal-Dual Approach 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.
Autoren/Hrsg.
Weitere Infos & Material
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
