Technical, Research Report
@TechReport
Technischer-, Forschungsbericht


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked





Author, Editor

Author(s):

Csaba, Bela
Lodha, Sachin

dblp
dblp



Editor(s):





BibTeX Citekey*:

Csaba2001

Language:

English

Title, Institution

Title*:

A randomized on-line algorithm for the k-server problem on a line

Institution*:

DIMACS-Center for Discrete Mathematics & Theoretical Computer Science

Publishers or Institutions Address*:

Piscataway, NJ

Type:

Technical Report

No, Year, pp.,

Number*:

DIMACS TechReport 2001-34

Pages*:

15

Month:

October

VG Wort
Pages*:


Year*:

2001

ISBN/ISSN:






DOI:




Note, Abstract, ©

Note:


(LaTeX) Abstract:

We give a $O(n^{2 \over 3}\log{n})$-competitive randomized $k$--server algorithm when the underlying metric space is given by $n$ equally spaced points on a line. For $n = k + o(k^{3 \over 2}/\log{k})$, this algorithm is $o(k)$--competitive.

Categories / Keywords:

on-line algorithms

Copyright Message:


HyperLinks / References / URLs:

ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-34.ps.gz

Personal Comments:


File Upload:


Download
Access Level:


Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:
@TECHREPORT{Csaba2001,
AUTHOR = {Csaba, Bela and Lodha, Sachin},
TITLE = {A randomized on-line algorithm for the k-server problem on a line},
YEAR = {2001},
TYPE = {Technical Report},
INSTITUTION = {DIMACS-Center for Discrete Mathematics & Theoretical Computer Science},
NUMBER = {DIMACS TechReport 2001-34},
PAGES = {15},
ADDRESS = {Piscataway, NJ},
MONTH = {October},
}


Entry last modified by Bela Csaba, 07/15/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
04/11/2003 04:30:17 PM
Revision
0.



Editor
Bela Csaba



Edit Date
04/11/2003 04:30:17 PM