Weighted k-server bounds via combinatorial dichotomies

N. Bansal; M. Elias; G. Koumoutsos

doi:10.1109/FOCS.2017.52

Weighted k-server bounds via combinatorial dichotomies

N. Bansal, M. Elias, G. Koumoutsos

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

13 Citations (Scopus)

Abstract

The weighted k-server problem is a natural generalization of the k-server problem where each server has a different weight. We consider the problem on uniform metrics, which corresponds to a natural generalization of paging. Our main result is a doubly exponential lower bound on the competitive ratio of any deterministic online algorithm, that essentially matches the known upper bounds for the problem and closes a large and long-standing gap. The lower bound is based on relating the weighted k-server problem to a certain combinatorial problem and proving a Ramsey-theoretic lower bound for it. This combinatorial connection also reveals several structural properties of low cost feasible solutions to serve a sequence of requests. We use this to show that the generalized Work Function Algorithm achieves an almost optimum competitive ratio, and to obtain new refined upper bounds on the competitive ratio for the case of d different weight classes.

Original language	English
Title of host publication	2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 15-17 October 2017, Berkeley, California
Place of Publication	Piscataway
Publisher	Institute of Electrical and Electronics Engineers
Pages	493-504
Number of pages	12
ISBN (Electronic)	978-1-5386-3464-6
ISBN (Print)	978-1-5386-3465-3
DOIs	https://doi.org/10.1109/FOCS.2017.52
Publication status	Published - 2017
Event	58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), October 15-17, 2017, Berkeley, California - DoubleTree Hotel at the Berkeley Marina, Berkeley, United States Duration: 15 Oct 2017 → 17 Oct 2017 https://focs17.simons.berkeley.edu/

Conference

Conference	58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), October 15-17, 2017, Berkeley, California
Abbreviated title	FOCS 2017
Country/Territory	United States
City	Berkeley
Period	15/10/17 → 17/10/17
Internet address	https://focs17.simons.berkeley.edu/

Keywords

competitive analysis
online algorithms
weighted k-server

Access to Document

10.1109/FOCS.2017.52

Cite this

@inproceedings{68c56b44fd2e40bd88e0b4d060a0b7d2,

title = "Weighted k-server bounds via combinatorial dichotomies",

abstract = "The weighted k-server problem is a natural generalization of the k-server problem where each server has a different weight. We consider the problem on uniform metrics, which corresponds to a natural generalization of paging. Our main result is a doubly exponential lower bound on the competitive ratio of any deterministic online algorithm, that essentially matches the known upper bounds for the problem and closes a large and long-standing gap. The lower bound is based on relating the weighted k-server problem to a certain combinatorial problem and proving a Ramsey-theoretic lower bound for it. This combinatorial connection also reveals several structural properties of low cost feasible solutions to serve a sequence of requests. We use this to show that the generalized Work Function Algorithm achieves an almost optimum competitive ratio, and to obtain new refined upper bounds on the competitive ratio for the case of d different weight classes.",

keywords = "competitive analysis, online algorithms, weighted k-server",

author = "N. Bansal and M. Elias and G. Koumoutsos",

year = "2017",

doi = "10.1109/FOCS.2017.52",

language = "English",

isbn = "978-1-5386-3465-3 ",

pages = "493--504",

booktitle = "2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 15-17 October 2017, Berkeley, California",

publisher = "Institute of Electrical and Electronics Engineers",

address = "United States",

note = "58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), October 15-17, 2017, Berkeley, California, FOCS 2017 ; Conference date: 15-10-2017 Through 17-10-2017",

url = "https://focs17.simons.berkeley.edu/",

}

Bansal, N, Elias, M & Koumoutsos, G 2017, Weighted k-server bounds via combinatorial dichotomies. in 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 15-17 October 2017, Berkeley, California., 8104084, Institute of Electrical and Electronics Engineers, Piscataway, pp. 493-504, 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), October 15-17, 2017, Berkeley, California, Berkeley, California, United States, 15/10/17. https://doi.org/10.1109/FOCS.2017.52

Weighted k-server bounds via combinatorial dichotomies. / Bansal, N.; Elias, M.; Koumoutsos, G.
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 15-17 October 2017, Berkeley, California. Piscataway: Institute of Electrical and Electronics Engineers, 2017. p. 493-504 8104084.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Weighted k-server bounds via combinatorial dichotomies

AU - Bansal, N.

AU - Elias, M.

AU - Koumoutsos, G.

PY - 2017

Y1 - 2017

N2 - The weighted k-server problem is a natural generalization of the k-server problem where each server has a different weight. We consider the problem on uniform metrics, which corresponds to a natural generalization of paging. Our main result is a doubly exponential lower bound on the competitive ratio of any deterministic online algorithm, that essentially matches the known upper bounds for the problem and closes a large and long-standing gap. The lower bound is based on relating the weighted k-server problem to a certain combinatorial problem and proving a Ramsey-theoretic lower bound for it. This combinatorial connection also reveals several structural properties of low cost feasible solutions to serve a sequence of requests. We use this to show that the generalized Work Function Algorithm achieves an almost optimum competitive ratio, and to obtain new refined upper bounds on the competitive ratio for the case of d different weight classes.

AB - The weighted k-server problem is a natural generalization of the k-server problem where each server has a different weight. We consider the problem on uniform metrics, which corresponds to a natural generalization of paging. Our main result is a doubly exponential lower bound on the competitive ratio of any deterministic online algorithm, that essentially matches the known upper bounds for the problem and closes a large and long-standing gap. The lower bound is based on relating the weighted k-server problem to a certain combinatorial problem and proving a Ramsey-theoretic lower bound for it. This combinatorial connection also reveals several structural properties of low cost feasible solutions to serve a sequence of requests. We use this to show that the generalized Work Function Algorithm achieves an almost optimum competitive ratio, and to obtain new refined upper bounds on the competitive ratio for the case of d different weight classes.

KW - competitive analysis

KW - online algorithms

KW - weighted k-server

UR - http://www.scopus.com/inward/record.url?scp=85041135097&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2017.52

DO - 10.1109/FOCS.2017.52

M3 - Conference contribution

SN - 978-1-5386-3465-3

SP - 493

EP - 504

BT - 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 15-17 October 2017, Berkeley, California

PB - Institute of Electrical and Electronics Engineers

CY - Piscataway

T2 - 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), October 15-17, 2017, Berkeley, California

Y2 - 15 October 2017 through 17 October 2017

ER -

Weighted k-server bounds via combinatorial dichotomies

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this