Randomized metarounding (extended abstract)

We exhibit an infinite doubling metric space (X,d) such that for any non-expansive f : X -> L₁, there exists a pair x,y ∈ X with d(x,y) arbitrarily large, and such that |f(x)-f(y)\|₁/d(x,y) ≲ √log log d(x,y)}/(log d(x,y)).

As a consequence, we show that ...

Improving a long chain of works we obtain a randomized EREW PRAM algorithm for finding the connected components of a graph G=(V,E) with n vertices and m edges in O(log n) time using an optimal number of O((m+n)/log n) processors. The result returned by ...

Let P be a linear relaxation of an integer polytope Z such that the integrality gap of P with respect to Z is at most r, as verified by a polytime heuristic A, which on any positive cost function c returns an integer solution (an extreme point of Z) ...