The design of competitive online algorithms via a primal-dual approach
著者
書誌事項
The design of competitive online algorithms via a primal-dual approach
（Foundations and trends in theoretical computer science, 3:2-3）
Now Publishers, c2009
大学図書館所蔵 件 / 全3件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
注記
Bibliography: p.171-176
内容説明・目次
内容説明
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
「Nielsen BookData」 より