K-servers with a smile: Online algorithms via projections

Niv Buchbinder; Anupam Gupta; Marco Molinaro; Joseph Naor

doi:10.1137/1.9781611975482.7

K-servers with a smile: Online algorithms via projections

Niv Buchbinder, Anupam Gupta, Marco Molinaro, Joseph Naor

Computer Science

Research output: Contribution to conference › Paper › peer-review

Abstract

We consider the k-server problem on trees and HSTs. We give an algorithm based on Bregman projections. This algorithm has a competitive ratios that match some of the recent results given by Bubeck et al. (STOC 2018), whose algorithm was based on mirror-descent-based continuous dynamics prescribed via a differential inclusion.

Original language	English (US)
Pages	98-116
Number of pages	19
DOIs	https://doi.org/10.1137/1.9781611975482.7
State	Published - 2019
Event	30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States Duration: Jan 6 2019 → Jan 9 2019

Conference

Conference	30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
Country/Territory	United States
City	San Diego
Period	1/6/19 → 1/9/19

ASJC Scopus subject areas

Software
General Mathematics

Access to Document

10.1137/1.9781611975482.7

Cite this

@conference{72a650479a3d40e7bfee4c485abe43bd,

title = "K-servers with a smile: Online algorithms via projections",

abstract = "We consider the k-server problem on trees and HSTs. We give an algorithm based on Bregman projections. This algorithm has a competitive ratios that match some of the recent results given by Bubeck et al. (STOC 2018), whose algorithm was based on mirror-descent-based continuous dynamics prescribed via a differential inclusion.",

author = "Niv Buchbinder and Anupam Gupta and Marco Molinaro and Joseph Naor",

note = "Publisher Copyright: Copyright {\textcopyright} 2019 by SIAM.; 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 ; Conference date: 06-01-2019 Through 09-01-2019",

year = "2019",

doi = "10.1137/1.9781611975482.7",

language = "English (US)",

pages = "98--116",

}

TY - CONF

T1 - K-servers with a smile

T2 - 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019

AU - Buchbinder, Niv

AU - Gupta, Anupam

AU - Molinaro, Marco

AU - Naor, Joseph

PY - 2019

Y1 - 2019

N2 - We consider the k-server problem on trees and HSTs. We give an algorithm based on Bregman projections. This algorithm has a competitive ratios that match some of the recent results given by Bubeck et al. (STOC 2018), whose algorithm was based on mirror-descent-based continuous dynamics prescribed via a differential inclusion.

AB - We consider the k-server problem on trees and HSTs. We give an algorithm based on Bregman projections. This algorithm has a competitive ratios that match some of the recent results given by Bubeck et al. (STOC 2018), whose algorithm was based on mirror-descent-based continuous dynamics prescribed via a differential inclusion.

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

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

U2 - 10.1137/1.9781611975482.7

DO - 10.1137/1.9781611975482.7

M3 - Paper

AN - SCOPUS:85066935067

SP - 98

EP - 116

Y2 - 6 January 2019 through 9 January 2019

ER -

K-servers with a smile: Online algorithms via projections

Abstract

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this