5 citations · 8 across the 4 of their papers we have counts for
7 papers
Metrical Service Systems with Transformations
Sébastien Bubeck, Niv Buchbinder, Christian Coester +1
We consider a generalization of the fundamental online metrical service systems (MSS) problem where the feasible region can be transformed between requests. In this problem, which…
Vertex Sparsification for Edge Connectivity
Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit +5
Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether -approximate cut-prese…
Online Multiserver Convex Chasing and Optimization
Sébastien Bubeck, Yuval Rabani, Mark Sellke
We introduce the problem of -chasing of convex functions, a simultaneous generalization of both the famous k-server problem in , and of the problem of chasing convex bodies…
Optimization of Mean-field Spin Glasses
Ahmed El Alaoui, Andrea Montanari, Mark Sellke
Mean-field spin glasses are families of random energy functions (Hamiltonians) on high-dimensional product spaces. In this paper we consider the case of Ising mixed -spin models…
Vertex Sparsifiers for c-Edge Connectivity
Yang P. Liu, Richard Peng, Mark Sellke
We show the existence of O(f(c)k) sized vertex sparsifiers that preserve all edge-connectivity values up to c between a set of k terminal vertices, where f(c) is a function that on…
Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without
Sébastien Bubeck, Yuanzhi Li, Yuval Peres +1
We consider the non-stochastic version of the (cooperative) multi-player multi-armed bandit problem. The model assumes no communication at all between the players, and furthermore…