19 citations · 30 across the 10 of their papers we have counts for
9 papers · 1 filter
Approximate in time -- now in any norm!
Thomas Rothvoss, Moritz Venzin
We show that a constant factor approximation of the shortest and closest lattice vector problem in any norm can be computed in time . This contrasts the correspondin…
Improved Analysis of Online Balanced Clustering
Marcin Bienkowski, Martin Böhm, Martin Koutecký +3
In the online balanced graph repartitioning problem, one has to maintain a clustering of nodes into clusters, each having nodes. During runtime, an online…
On the Hardness of Scheduling With Non-Uniform Communication Delays
Sami Davies, Janardhan Kulkarni, Thomas Rothvoss +3
In the scheduling with non-uniform communication delay problem, the input is a set of jobs with precedence constraints. Associated with every precedence constraint between a pair o…
Scheduling with Communication Delays via LP Hierarchies and Clustering
Sami Davies, Janardhan Kulkarni, Thomas Rothvoss +2
We consider the classic problem of scheduling jobs with precedence constraints on identical machines to minimize makespan, in the presence of communication delays. In this setting,…
Linear Size Sparsifier and the Geometry of the Operator Norm Ball
Victor Reis, Thomas Rothvoss
The Matrix Spencer Conjecture asks whether given symmetric matrices in with eigenvalues in one can always find signs so that their signed sum…
Lecture Notes on the ARV Algorithm for Sparsest Cut
Thomas Rothvoss
One of the landmarks in approximation algorithms is the -approximation algorithm for the Uniform Sparsest Cut problem by Arora, Rao and Vazirani from 2004. The al…