On space bounded server algorithms

G. R. Baliga, A. M. Shende

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

This paper is motivated by the need for fast algorithms for online problems, many of which require algorithms to provide solutions in real time. We study a class of arguably fast algorithms (called space bounded algorithms) for the k-server problem on finite metric spaces. Specifically, we provide a necessary and sufficient condition for such algorithms to be competitive on finite metric spaces. Moreover, this characterization provides a strategy for designing competitive algorithms for finite metric spaces.

Original languageEnglish (US)
Title of host publicationProceedings - ICCI 1993
Subtitle of host publication5th International Conference on Computing and Information
EditorsWaldemar W. Koczkodaj, Osman Abou-Rabia, Carl K. Chang
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages77-81
Number of pages5
ISBN (Electronic)0818642122, 9780818642128
DOIs
StatePublished - 1993
Externally publishedYes
Event5th International Conference on Computing and Information, ICCI 1993 - Sudbury, Canada
Duration: May 27 1993May 29 1993

Publication series

NameProceedings - ICCI 1993: 5th International Conference on Computing and Information

Conference

Conference5th International Conference on Computing and Information, ICCI 1993
Country/TerritoryCanada
CitySudbury
Period5/27/935/29/93

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Information Systems
  • Software
  • Modeling and Simulation

Fingerprint

Dive into the research topics of 'On space bounded server algorithms'. Together they form a unique fingerprint.

Cite this