Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
Share this page via the icons above, or by copying the link below:
Copy To Clipboard
Successfully Copied!
On-line Algorithms
 
A co-publication of the AMS, DIMACS, and Association for Computing Machinery
On-line Algorithms
On-line Algorithms
Hardcover ISBN:  978-0-8218-6596-5
Product Code:  DIMACS/7
List Price: $48.00
MAA Member Price: $43.20
AMS Member Price: $38.40
eBook ISBN:  978-1-4704-3965-1
Product Code:  DIMACS/7.E
List Price: $45.00
MAA Member Price: $40.50
AMS Member Price: $36.00
Hardcover ISBN:  978-0-8218-6596-5
eBook: ISBN:  978-1-4704-3965-1
Product Code:  DIMACS/7.B
List Price: $93.00$70.50
MAA Member Price: $83.70$63.45
AMS Member Price: $74.40$56.40
On-line Algorithms
Click above image for expanded view
On-line Algorithms
On-line Algorithms
A co-publication of the AMS, DIMACS, and Association for Computing Machinery
Hardcover ISBN:  978-0-8218-6596-5
Product Code:  DIMACS/7
List Price: $48.00
MAA Member Price: $43.20
AMS Member Price: $38.40
eBook ISBN:  978-1-4704-3965-1
Product Code:  DIMACS/7.E
List Price: $45.00
MAA Member Price: $40.50
AMS Member Price: $36.00
Hardcover ISBN:  978-0-8218-6596-5
eBook ISBN:  978-1-4704-3965-1
Product Code:  DIMACS/7.B
List Price: $93.00$70.50
MAA Member Price: $83.70$63.45
AMS Member Price: $74.40$56.40
  • Book Details
     
     
    DIMACS - Series in Discrete Mathematics and Theoretical Computer Science
    Volume: 71992; 179 pp
    MSC: Primary 05; 68; 90;

    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.

  • Table of Contents
     
     
    • Chapters
    • A graph-theoretic game and its application to the $k$-server problem (extended abstract)
    • The server problem and on-line games
    • The harmonic online $K$-server algorithm is competitive
    • The $K$-server dual and loose competitiveness for paging
    • A statistical adversary for on-line algorithms
    • On-line graph coloring
    • Online weighted matching
    • On the competitiveness of splay trees: Relations to the union-find problem
    • Competitive group testing
    • Randomized algorithms for multiprocessor page migration
    • Navigating in unfamiliar geometric terrain (extended summary)
    • Visual searching and mapping
    • Scheduling parallel machines on-line
    • Competitive paging with locality of reference (brief summary)
    • Lower bounds for on-line graph coloring
  • Requests
     
     
    Review Copy – for publishers of book reviews
    Accessibility – to request an alternate format of an AMS title
Volume: 71992; 179 pp
MSC: Primary 05; 68; 90;

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.

  • Chapters
  • A graph-theoretic game and its application to the $k$-server problem (extended abstract)
  • The server problem and on-line games
  • The harmonic online $K$-server algorithm is competitive
  • The $K$-server dual and loose competitiveness for paging
  • A statistical adversary for on-line algorithms
  • On-line graph coloring
  • Online weighted matching
  • On the competitiveness of splay trees: Relations to the union-find problem
  • Competitive group testing
  • Randomized algorithms for multiprocessor page migration
  • Navigating in unfamiliar geometric terrain (extended summary)
  • Visual searching and mapping
  • Scheduling parallel machines on-line
  • Competitive paging with locality of reference (brief summary)
  • Lower bounds for on-line graph coloring
Review Copy – for publishers of book reviews
Accessibility – to request an alternate format of an AMS title
Please select which format for which you are requesting permissions.