Title	k-server via multi-scale entropic regulariziation
Creator	Lee, James
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2017-11-14T11:02
Description	The k-server problem is one of the most well-known and widely studied problems in online algorithms. We present an O(log k)^2-competitive randomized algorithm for the k-server problem on HSTs. A breakthrough of Bansal, Buchbinder, Madry, and Naor gave a poly(log k, log N)-competitive algorithm for HSTs of size N, but no o(k)-competitive algorithm that doesn't depend on N was known. Using this, we obtain a poly(log k, log D)-competitive algorithm for any metric space X, where D is the ratio of the largest to smallest distance in X. Our approach is an instantiation of online mirror descent where the mirror map is a multi-scale entropy. Joint work with Sebastien Bubeck, Michael Cohen, Yin Tat Lee, and Aleksander Madry.
Extent	33 minutes
Subject	Mathematics; Computer science; Operations research, mathematical programming; Theoretical computer science
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: University of Washington
Series	BIRS Workshop Lecture Videos (Banff, Alta)
Date Available	2018-05-14
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0366269
URI	http://hdl.handle.net/2429/65837
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Faculty
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos

k-server via multi-scale entropic regulariziation Lee, James

Description

Item Metadata

Item Media

Item Citations and Data

Rights