On space bounded server algorithms

G. R. Baliga; A. M. Shende

doi:10.1109/ICCI.1993.315400

On space bounded server algorithms

G. R. Baliga, A. M. Shende

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 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 language	English (US)
Title of host publication	Proceedings - ICCI 1993
Subtitle of host publication	5th International Conference on Computing and Information
Editors	Waldemar W. Koczkodaj, Osman Abou-Rabia, Carl K. Chang
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	77-81
Number of pages	5
ISBN (Electronic)	0818642122, 9780818642128
DOIs	https://doi.org/10.1109/ICCI.1993.315400
State	Published - 1993
Externally published	Yes
Event	5th International Conference on Computing and Information, ICCI 1993 - Sudbury, Canada Duration: May 27 1993 → May 29 1993

Publication series

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

Conference

Conference	5th International Conference on Computing and Information, ICCI 1993
Country/Territory	Canada
City	Sudbury
Period	5/27/93 → 5/29/93

All Science Journal Classification (ASJC) codes

Computational Theory and Mathematics
Information Systems
Software
Modeling and Simulation

Access to Document

10.1109/ICCI.1993.315400

Cite this

Baliga, G. R., & Shende, A. M. (1993). On space bounded server algorithms. In W. W. Koczkodaj, O. Abou-Rabia, & C. K. Chang (Eds.), Proceedings - ICCI 1993: 5th International Conference on Computing and Information (pp. 77-81). Article 315400 (Proceedings - ICCI 1993: 5th International Conference on Computing and Information). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICCI.1993.315400

Baliga, G. R. ; Shende, A. M. / On space bounded server algorithms. Proceedings - ICCI 1993: 5th International Conference on Computing and Information. editor / Waldemar W. Koczkodaj ; Osman Abou-Rabia ; Carl K. Chang. Institute of Electrical and Electronics Engineers Inc., 1993. pp. 77-81 (Proceedings - ICCI 1993: 5th International Conference on Computing and Information).

@inproceedings{e86b5cb2222f40639f1a3ab68df72c8a,

title = "On space bounded server algorithms",

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.",

author = "Baliga, \{G. R.\} and Shende, \{A. M.\}",

note = "Publisher Copyright: {\textcopyright} 1993 IEEE.; 5th International Conference on Computing and Information, ICCI 1993 ; Conference date: 27-05-1993 Through 29-05-1993",

year = "1993",

doi = "10.1109/ICCI.1993.315400",

language = "English (US)",

series = "Proceedings - ICCI 1993: 5th International Conference on Computing and Information",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "77--81",

editor = "Koczkodaj, \{Waldemar W.\} and Osman Abou-Rabia and Chang, \{Carl K.\}",

booktitle = "Proceedings - ICCI 1993",

address = "United States",

}

Baliga, GR & Shende, AM 1993, On space bounded server algorithms. in WW Koczkodaj, O Abou-Rabia & CK Chang (eds), Proceedings - ICCI 1993: 5th International Conference on Computing and Information., 315400, Proceedings - ICCI 1993: 5th International Conference on Computing and Information, Institute of Electrical and Electronics Engineers Inc., pp. 77-81, 5th International Conference on Computing and Information, ICCI 1993, Sudbury, Canada, 5/27/93. https://doi.org/10.1109/ICCI.1993.315400

On space bounded server algorithms. / Baliga, G. R.; Shende, A. M.
Proceedings - ICCI 1993: 5th International Conference on Computing and Information. ed. / Waldemar W. Koczkodaj; Osman Abou-Rabia; Carl K. Chang. Institute of Electrical and Electronics Engineers Inc., 1993. p. 77-81 315400 (Proceedings - ICCI 1993: 5th International Conference on Computing and Information).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On space bounded server algorithms

AU - Baliga, G. R.

AU - Shende, A. M.

PY - 1993

Y1 - 1993

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85064515556

UR - https://www.scopus.com/inward/citedby.url?scp=85064515556&partnerID=8YFLogxK

U2 - 10.1109/ICCI.1993.315400

DO - 10.1109/ICCI.1993.315400

M3 - Conference contribution

AN - SCOPUS:85064515556

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

SP - 77

EP - 81

BT - Proceedings - ICCI 1993

A2 - Koczkodaj, Waldemar W.

A2 - Abou-Rabia, Osman

A2 - Chang, Carl K.

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 5th International Conference on Computing and Information, ICCI 1993

Y2 - 27 May 1993 through 29 May 1993

ER -

Baliga GR, Shende AM. On space bounded server algorithms. In Koczkodaj WW, Abou-Rabia O, Chang CK, editors, Proceedings - ICCI 1993: 5th International Conference on Computing and Information. Institute of Electrical and Electronics Engineers Inc. 1993. p. 77-81. 315400. (Proceedings - ICCI 1993: 5th International Conference on Computing and Information). doi: 10.1109/ICCI.1993.315400

On space bounded server algorithms

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this