James R. Lee

activity

20042022

most citedMeasured descent: A new embedding method for finite metrics

72 citations · 223 across the 37 of their papers we have counts for

collaborators

Showing cs.DSShow all

8 papers · 1 filter

cs.DS2021

Multiscale entropic regularization for MTS on general metric spaces

Farzam Ebrahimnejad, James R. Lee

We present an $O ((lo g n)^{2})$ -competitive algorithm for metrical task systems (MTS) on any $n$ -point metric space that is also $1$ -competitive for service costs. This matches the c…

cs.DS2019★ 10 cited

Pure entropic regularization for metrical task systems

Christian Coester, James R. Lee

We show that on every $n$ -point HST metric, there is a randomized online algorithm for metrical task systems (MTS) that is $1$ -competitive for service costs and $O (lo g n)$ -competi…

cs.DS2018

Flow-Cut Gaps and Face Covers in Planar Graphs

Robert Krauthgamer, James R. Lee, Havana Rika

The relationship between the sparsest cut and the maximum concurrent multi-flow in graphs has been studied extensively. For general graphs with $k$ terminal pairs, the flow-cut gap…

cs.DS2018

Metrical task systems on trees via mirror descent and unfair gluing

Sébastien Bubeck, Michael B. Cohen, James R. Lee +1

We consider metrical task systems on tree metrics, and present an $O (depth \times lo g n)$ -competitive randomized algorithm based on the mirror descent framework introduce…

cs.DS2017

k-server via multiscale entropic regularization

Sebastien Bubeck, Michael B. Cohen, James R. Lee +2

We present an $O ((lo g k)^{2})$ -competitive randomized algorithm for the $k$ -server problem on hierarchically separated trees (HSTs). This is the first $o (k)$ -competitive randomized…

cs.DS2017

Fusible HSTs and the randomized k-server conjecture

James R. Lee

We exhibit an $O ((lo g k)^{6})$ -competitive randomized algorithm for the $k$ -server problem on any metric space. It is shown that a potential-based algorithm for the fractional $k$ -s…