Muutke küpsiste eelistusi

Introduction to Online Computation: Determinism, Randomization, Advice 1st ed. 2016 [Kõva köide]

  • Formaat: Hardback, 349 pages, kõrgus x laius: 235x155 mm, kaal: 6742 g, 58 Illustrations, black and white; XV, 349 p. 58 illus., 1 Hardback
  • Sari: Texts in Theoretical Computer Science. An EATCS Series
  • Ilmumisaeg: 10-Nov-2016
  • Kirjastus: Springer International Publishing AG
  • ISBN-10: 3319427474
  • ISBN-13: 9783319427478
Teised raamatud teemal:
  • Kõva köide
  • Hind: 85,76 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Tavahind: 100,89 €
  • Säästad 15%
  • Raamatu kohalejõudmiseks kirjastusest kulub orienteeruvalt 2-4 nädalat
  • Kogus:
  • Lisa ostukorvi
  • Tasuta tarne
  • Tellimisaeg 2-4 nädalat
  • Lisa soovinimekirja
Introduction to Online Computation: Determinism, Randomization, Advice 1st ed. 2016Suurem pilt
  • Formaat: Hardback, 349 pages, kõrgus x laius: 235x155 mm, kaal: 6742 g, 58 Illustrations, black and white; XV, 349 p. 58 illus., 1 Hardback
  • Sari: Texts in Theoretical Computer Science. An EATCS Series
  • Ilmumisaeg: 10-Nov-2016
  • Kirjastus: Springer International Publishing AG
  • ISBN-10: 3319427474
  • ISBN-13: 9783319427478
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9783319427478.html
Märksõnad:
This textbook explains online computation in different settings, with particular emphasis on randomization and advice complexity. These settings are analyzed for various online problems such as the paging problem, the k-server problem, job shop scheduling, the knapsack problem, the bit guessing problem, and problems on graphs.

This book is appropriate for undergraduate and graduate students of computer science, assuming a basic knowledge in algorithmics and discrete mathematics. Also researchers will find this a valuable reference for the recent field of advice complexity.

Arvustused

This book is about online algorithms for optimization problems. The book can be used as a textbook on the undergraduate level. The book can also be used for self-study and as a reference. Its strength in this regard is enhanced by the historical notes at the end of each chapter and a comprehensive bibliography. (Bogdan S. Chlebus,Mathematical Reviews, March, 2018)

This text is an important contribution to the field of online algorithms. Without a doubt, this text is a must-read for anyone seriously pursuing the analysis of algorithms, particularly online versions of those algorithms. (Michael Goldberg and R. Goldberg, Computing Reviews, October, 2017)

1 Introduction
1(30)
1.1 Offline Algorithms
2(7)
1.2 Online Algorithms and Paging
9(10)
1.3 An Upper Bound for Paging
19(2)
1.4 A Lower Bound for Paging
21(4)
1.5 Marking Algorithms
25(2)
1.6 Refined Competitive Analysis
27(1)
1.6.1 Lookahead
27(1)
1.6.2 Resource Augmentation
27(1)
1.7 Historical and Bibliographical Notes
28(3)
2 Randomization
31(54)
2.1 Introduction
32(8)
2.2 A Randomized Online Algorithm for Paging
40(4)
2.3 Yao's Principle
44(11)
2.3.1 Finite Problems
45(5)
2.3.2 Infinite Problems
50(2)
*2.3.3 Unbounded Problems
52(3)
2.4 Another Point of View: Game Theory
55(5)
2.5 A Lower Bound for Randomized Online Algorithms for Paging
60(16)
*2.6 A Barely Random Algorithm for Paging
64(8)
*2.7 Bounds with Probability Tending to One
72(4)
2.8 The Ski Rental Problem
76(6)
2.9 Historical and Bibliographical Notes
82(3)
3 Advice Complexity
85(28)
3.1 Introduction
86(4)
3.2 Self-Delimiting Encoding of Strings
90(3)
3.3 Proving Lower Bounds
93(2)
3.4 The Advice Complexity of Paging
95(10)
3.4.1 Optimality
96(6)
3.4.2 Small Competitive Ratio
102(3)
3.5 Advice and Randomization
105(5)
3.6 Historical and Bibliographical Notes
110(3)
4 The k-Server Problem
113(42)
4.1 Introduction
114(3)
4.2 A Lower Bound for Deterministic Algorithms
117(4)
4.3 Potential Functions
121(3)
4.4 k-Server on the Line
124(5)
4.5 k-Server on Trees
129(3)
4.6 Advice Complexity
132(21)
4.6.1 Optimality for the General Case
132(6)
4.6.2 Optimality for the Line
138(2)
4.6.3 An Upper Bound for the Euclidean Plane
140(4)
*4.6.4 An Upper Bound for the General Case
144(9)
4.6.5 Advice and the Randomized k-Server Conjecture
153(1)
4.7 Historical and Bibliographical Remarks
153(2)
5 Job Shop Scheduling
155(28)
5.1 Introduction
156(4)
5.2 Deterministic Algorithms
160(8)
5.3 Randomized Algorithms
168(4)
5.3.1 A One-Competitive Randomized Algorithm
170(1)
5.3.2 Bounds with Probability Tending to One
170(1)
5.3.3 A Barely Random Algorithm
171(1)
5.4 Advice Complexity
172(9)
5.4.1 Optimality
172(4)
5.4.2 Small Competitive Ratio
176(5)
5.5 Historical and Bibliographical Notes
181(2)
6 The Knapsack Problem
183(28)
6.1 Introduction
184(1)
6.2 Deterministic Algorithms
185(2)
6.3 Advice Complexity
187(6)
6.3.1 Optimality
187(1)
6.3.2 Small Advice
188(1)
6.3.3 Logarithmic Advice
189(4)
6.4 Randomized Algorithms
193(4)
6.4.1 A Barely Random Algorithm
193(3)
6.4.2 A Lower Bound for Randomized Algorithms
196(1)
6.5 Resource Augmentation
197(5)
6.6 The General Case
202(8)
6.6.1 Advice Complexity
203(5)
6.6.2 Randomized Online Algorithms
208(1)
6.6.3 Resource Augmentation
209(1)
6.7 Historical and Bibliographical Notes
210(1)
7 The Bit Guessing Problem
211(30)
7.1 Introduction
212(1)
7.2 Deterministic and Randomized Algorithms
213(1)
7.3 Advice Complexity
214(12)
7.4 Advice-Preserving Reductions
226(14)
7.4.1 The k-Server Problem
227(3)
7.4.2 The Set Cover Problem
230(5)
7.4.3 The Disjoint Path Allocation Problem
235(5)
7.5 Historical and Bibliographical Notes
240(1)
8 Problems on Graphs
241(28)
8.1 Introduction
242(1)
8.2 The Coloring Problem
243(8)
8.2.1 Deterministic Algorithms
244(5)
8.2.2 Advice Complexity
249(2)
8.3 The Minimum Spanning Tree Problem
251(15)
8.3.1 Deterministic and Randomized Algorithms
251(2)
8.3.2 Advice Complexity
253(4)
8.3.3 Special Graph Classes
257(9)
8.4 Historical and Bibliographical Notes
266(3)
Solutions to Exercises 269(54)
Glossary 323(4)
Bibliography 327(14)
Index 341
Dr. Dennis Komm is a lecturer in the Chair of Information Technology and Education at ETH Zürich. His research interests include approximation algorithms for hard optimization problems, re-optimization of optimization problems, and advice complexity in different setups and environments.