AMS Bookstore LOGO amslogo
Return to List

AMS TextbooksAMS Applications-related Books

On-line Algorithms
Edited by: Lyle A. McGeoch and Daniel D. Sleator
A co-publication of the AMS, DIMACS, and Association for Computing Machinery.

DIMACS: Series in Discrete Mathematics and Theoretical Computer Science
1992; 179 pp; hardcover
Volume: 7
ISBN-10: 0-8218-6596-X
ISBN-13: 978-0-8218-6596-5
List Price: US$40
Member Price: US$32
Order Code: DIMACS/7
[Add Item]

This volume contains the proceedings of the Workshop on On-line Algorithms held at the DIMACS Center at Rutgers University in February 1991. Presenting 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.

Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1-7 were co-published with the Association for Computer Machinery (ACM).

Table of Contents

  • N. Alon, R. M. Karp, D. Peleg, and D. West -- A graph-theoretic game and its application to the \(k\)-server problem (extended abstract)
  • M. Chrobak and L. L. Larmore -- The server problem and on-line games
  • E. F. Grove -- The harmonic online \(K\)-server algorithm is competitive
  • N. Young -- The \(K\)-server dual and loose competitiveness for paging
  • P. Raghavan -- A statistical adversary for on-line algorithms
  • H. A. Kierstead and W. T. Trotter -- On-line graph coloring
  • B. Kalyanasundaram and K. Pruhs -- Online weighted matching
  • J. M. Lucas -- On the competitiveness of splay trees: Relations to the union-find problem
  • D. Z. Du and F. K. Hwang -- Competitive group testing
  • J. Westbrook -- Randomized algorithms for multiprocessor page migration
  • A. Blum, P. Raghavan, and B. Schieber -- Navigating in unfamiliar geometric terrain (extended summary)
  • B. Kalyanasundaram and K. Pruhs -- Visual searching and mapping
  • D. B. Shmoys, J. Wein, and D. P. Williamson -- Scheduling parallel machines on-line
  • A. Borodin, S. Irani, P. Raghavan, and B. Schieber -- Competitive paging with locality of reference (brief summary)
  • M. M. Halldórsson and M. Szegedy -- Lower bounds for on-line graph coloring
Powered by MathJax

  AMS Home | Comments:
© Copyright 2014, American Mathematical Society
Privacy Statement

AMS Social

AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia