On-Line Algorithms

Erscheinungsjahr 1992
ISBN: 978-0-8218-6596-5
Verlag: American Mathematical Society

Buch, Englisch

This volume contains the proceedings of the Workshop on On-line Algorithms held at the DIMACS Center at Rutgers University in February 1991. Presenting new results in the theory of on-line algorithms, the articles discuss a broad range of problems. Most of the papers are based on competitive (worst-case) analysis of on-line algorithms, but some papers consider alternative approaches to on-line analysis. A critical question examined by some of the authors is how to modify competitive analysis to better reconcile the theory and practice of on-line algorithms. Many of the papers examine the ways in which randomization can be used to yield algorithms with improved performance. This book is aimed primarily at specialists in algorithm analysis, but most of the articles present clear expositions of previous work.

Fachgebiete

• Mathematik | Informatik Mathematik Mathematik Allgemein Grundlagen der Mathematik
• Mathematik | Informatik EDV | Informatik Daten / Datenbanken Automatische Datenerfassung, Datenanalyse

Inhaltsverzeichnis

Noga Alon, Richard M Karp, David Peleg, and Douglas West, A graph-theoretic game and its application to the k-server problem (extended abstract): Marek Chrobak and Lawrence L Larmore, The server problem and on-line games; E F Grove, The harmonic online K-server algorithm is competitive; Neal Young, The K-server dual and loose competitiveness for paging; Prabhakar Raghavan, A statistical adversary for on-line algorithms; H A Kierstead and W T Trotter, On-line graph coloring; Bala Kalyanasundaram and Kirk Pruhs, Online weighted matching; Joan M Lucas, On the competitiveness of splay trees: Relations to the union-find problem; D Z Du and F K Hwang, Competitive group testing; Jeffrey Westbrook, Randomized algorithms for multiprocessor page migration; Avrim Blum, Prabhaker Raghavan, and Baruch Schiever, Navigating in unfamiliar geometric terrain (extended summary); Bala Kalyanasundaram and Kirk Pruhs, Visual searching and mapping; David B Shmoys, Joel Wein, and David P Williamson, Scheduling parallel machines on-line; Allan Borodin, Sandy Irani, Prabhakar Raghavan, and Baruch Scheiber, Competitive paging with locality of reference (brief summary); Magnus M Halldorsson and Mario Szegedy, Lower bounds for on-line graph coloring.

This volume contains the proceedings of the Workshop on On-line Algorithms held at the DIMACS Center at Rutgers University in February 1991. Presenting new results in the theory of on-line algorithms, the articles discuss a broad range of problems. Most of the papers are based on competitive (worst-case) analysis of on-line algorithms, but some consider alternative approaches. This book is aimed primarily at specialists in algorithm analysis, but most of the articles present clear expositions of previous work.