| 书目名称 | Online Algorithms | | 副标题 | The State of the Art | | 编辑 | Amos Fiat,Gerhard J. Woeginger | | 视频video | http://file.papertrans.cn/702/701502/701502.mp4 | | 丛书名称 | Lecture Notes in Computer Science | | 图书封面 |  | | 描述 | This coherent anthology presents the state of the art in the booming area of online algorithms and competitive analysis of such algorithms. The 17 papers are carefully revised and thoroughly improved versions of presentations given first during a Dagstuhl seminar in 1996..An overview by the volume editors introduces the area to the reader. The technical chapters are devoted to foundational and methodological issues for the design and analysis of various classes of online algorithms as well as to the detailed evaluation of algorithms for various activities in online processing, ranging from load balancing and scheduling to networking and financial problems. An outlook by the volume editors and a bibliography listing more than 750 references complete the work..The book is ideally suited for advanced courses and self-study in online algorithms. It is indispensable reading for researchers and professionals active in the area. | | 出版日期 | Book 1998 | | 关键词 | Distributed Algorithms; Online Load Balancing; Online Navigation; Online Network Routing; Online Schedul | | 版次 | 1 | | doi | https://doi.org/10.1007/BFb0029561 | | isbn_softcover | 978-3-540-64917-5 | | isbn_ebook | 978-3-540-68311-7Series ISSN 0302-9743 Series E-ISSN 1611-3349 | | issn_series | 0302-9743 | | copyright | Springer-Verlag Berlin Heidelberg 1998 |
| 1 |
Front Matter |
|
|
Abstract
|
| 2 |
,Competitive analysis of algorithms, |
Amos Fiat,Gerhard J. Woeginger |
|
Abstract
|
| 3 |
,Self-organizing data structures, |
Susanne Albers,Jeffery Westbrook |
|
Abstract
|
| 4 |
,Competitive analysis of paging, |
Sandy Irani |
|
Abstract
|
| 5 |
,Metrical task systems, the server problem and the work function algorithm, |
Marek Chrobak,Lawrence L. Larmore |
|
Abstract
|
| 6 |
,Distributed paging, |
Yair Bartal |
|
Abstract
|
| 7 |
,Competitive analysis of distributed algorithms, |
James Aspnes |
|
Abstract
|
| 8 |
,On-line packing and covering problems, |
János Csirik,Gerhard J. Woeginger |
|
Abstract
|
| 9 |
,On-line load balancing, |
Yossi Azar |
|
Abstract
|
| 10 |
,On-line scheduling, |
JiŘí Sgall |
|
Abstract
We have seen a variety of on-line scheduling problems. Many of them are understood satisfactorily, but there are also many interesting open problems. Studied scheduling problems differ not only in the setting and numerical results, but also in the techniques used. In this way on-line scheduling illustrates many general aspects of competitive analysis.
|
| 11 |
,On-line searching and navigation, |
Piotr Berman |
|
Abstract
|
| 12 |
,On-line network routing, |
Stefano Leonardi |
|
Abstract
In this chapter we have described competitive on-line algorithms for on-line network routing problems. We have concentrated on routing in electrical and optical networks, presented algorithms for load minimization and throughput maximization problems, and mentioned some of the most popular open problems in the area..We have often referred to idealized models of communication networks. It is still open the issue of using many of these ideas to design more efficient algorithms in practical existing networks. A first relevant issue in this direction is to devise efficient distributed implementations of competitive on-line network routing algorithms.
|
| 13 |
,On-line network optimization problems, |
Bala Kalyanasundaram,Kirk Pruhs |
|
Abstract
There has been a reasonable amount of work on on-line network optimization in the monotone model. Usually one first analyzes the greedy algorithm that lets .. be the cheapest extension of ... Some reasonable fraction of the time the greedy algorithm turns out to be close to optimal. Even if it isn‘t, the analysis usually provides good intuition for developing a better algorithm. Often this better algorithm is relatively a minor modification to greedy..There has been much less work in the fixed quality and fixed cost models. This is probably the area where there is the greatest need for further investigation. The obvious greedy algorithm in the fixed quality model is to have .. be the cheapest modification of .. that satisfies the quality constant. Analogously, the obvious greedy algorithm in the fixed cost model is to have .. be the solution closest to optimal that can be obtained from .. within the cost bound. As a first step, one should probably try to analyze these greedy algorithms. The scant evidence available to date [10, 12] suggests that perhaps the greedy algorithms in the fixed cost and fixed quality models will be less likely to be close to optimally competitive than in
|
| 14 |
,Coloring graphs on-line, |
Hal A. Kierstead |
|
Abstract
|
| 15 |
,On-Line Algorithms in Machine Learning, |
Avrim Blum |
|
Abstract
|
| 16 |
,Competitive solutions for on-line financial problems, |
Ran El-Yaniv |
|
Abstract
|
| 17 |
,On the performance of competitive algorithms in practice, |
Anna R. Karlin |
|
Abstract
|
| 18 |
,Competitive odds and ends, |
Amos Fiat,Gerhard J. Woeginger |
|
Abstract
|
| 19 |
Back Matter |
|
|
Abstract
|
|
|
|Archiver|手机版|小黑屋|
派博传思国际
( 京公网安备110108008328)
GMT+8, 2025-7-23 04:55
发表于 2025-3-21 17:13:44
