Publications

We consider metrical task systems on tree metrics, and present an $O(\mathrm{depth} \times \log n)$-competitive randomized algorithm based on the mirror descent framework. For the special case of HSTs, we refine the standard approach based on combining unfair metrical task systems, yielding an $O(\log n)$-competitive algorithm. This is tight up to the implicit constant factor. Using known random embeddings of finite metric spaces into HSTs, this yields an $O((\log n)^2)$-competitive algorithm for general $n$-point spaces.

We give an \(O((\log k)^6)\)-competitive randomized algorithm for the k-server problem on general metric spaces. The best previous result independent of the underlying metric space is the 2k-1 competitive ratio established for the deterministic work function algorithm by Koutsoupias and Papadimitriou (1995).

Since deterministic algorithms can do no better than k on any metric space with at least k+1 points, this establishes that for every metric space on which the problem is non-trivial, randomized algorithms give an exponential improvement over determinsitic algorithms. The approach is via reduction to potential-based algorithms for the fractional k-server problem on ultrametrics.

We present an \(O((\log k)^2)\)-competitive randomized algorithm for the k-server problem on hierarchically separated trees (HSTs). This is the first o(k)-competitive randomized algorithm for which the competitive ratio is independent of the size of the underlying HST. Our algorithm is designed in the framework of online mirror descent where the mirror map is a multiscale entropy.

When combined with Bartal’s static HST embedding reduction, this leads to an \(O((\log k)^2 \log n)\)-competitive algorithm on any n-point metric space. We give a new dynamic HST embedding that yields an \(O((\log k)^3 \log \Delta)\)-competitive algorithm on any metric space where the ratio of the largest to smallest non-zero distance is at most \(\Delta\).

We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on n-vertex graphs are not the linear image of the feasible region of any SDP (i.e., any spectrahedron) of dimension less than \(2^{n^c}\), for some constant \(c > 0\). This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit family of polytopes.

Our results follow from a general technique for proving lower bounds on the positive semidefinite rank of a matrix. To this end, we establish a close connection between arbitrary SDPs and those arising from the sum-of-squares SDP hierarchy. For approximating maximum constraint satisfaction problems, we prove that SDPs of polynomial-size are equivalent in power to those arising from degree-O(1) sum-of-squares relaxations. This result implies, for instance, that no family of polynomial-size SDP relaxations can achieve better than a 7/8-approximation for MAX-3-SAT.

[ PPT slides ]

Best paper award, STOC 2015

We study the computational power of general symmetric relaxations for combinatorial optimization problems, both in the linear programming (LP) and semidefinite programming (SDP) case. We show new connections to explicit LP and SDP relaxations, like those obtained from standard hierarchies.

We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, polynomial-sized linear programs are exactly as powerful as programs arising from a constant number of rounds of the Sherali-Adams hierarchy. In particular, any polynomial-sized linear program for Max Cut has an integrality gap of 1/2 and any such linear program for Max 3-Sat has an integrality gap of 7/8.

Video: Linear programming and constraint satisfaction (Simons Institute)

The classical Okamura-Seymour theorem states that for an edge-capacitated, multi-commodity flow instance in which all terminals lie on a single face of a planar graph, there exists a feasible concurrent flow if and only if the cut conditions are satisfied. Simple examples show that a similar theorem is impossible in the node-capacitated setting. Nevertheless, we prove that an approximate flow/cut theorem does hold: For some universal c > 0, if the node cut conditions are satisfied, then one can simultaneously route a c-fraction of all the demands.

This answers an open question of Chekuri and Kawarabayashi. More generally, we show that this holds in the setting of multi-commodity polymatroid networks introduced by Chekuri, et. al. Our approach employs a new type of random metric embedding in order to round the convex programs corresponding to these more general flow problems.

We study the quantitative geometry of graphs in terms of their genus, using the structure of certain cut graphs. These are subgraphs whose removal leaves a planar graph.

Indyk and Sidiropoulos (2007) proved that any orientable graph of genus $g$ can be probabilistically embedded into a graph of genus $g−1$ with constant distortion. Viewing a graph of genus $g$ as embedded on the surface of a sphere with $g$ handles attached, Indyk and Sidiropoulos’ method gives an embedding into a distribution over planar graphs with distortion $O(g)$ by iteratively removing the handles. By removing all g handles at once, we present a probabilistic embedding with distortion $O(g^2)$ for both orientable and non-orientable graphs. Our result is obtained by showing that the nimum-cut graph of Erickson and Har Peled (2004) has low dilation, and then randomly cutting this graph out of the surface using the Peeling Lemma of Lee and Sidiropoulos (2009).

We prove that the function \(d : \mathbb{R}^3 \times \mathbb{R}^3 \to [0,\infty)\) given by

is a metric on \(\mathbb{R}^3\) such that \((\mathbb{R}^3, \sqrt{d})\) is isometric to a subset of Hilbert space, yet \((\mathbb{R}^3,d)\) does not admit a bi-Lipschitz embedding into \(L_1\). This yields a new simple counter example to the Goemans-Linial conjecture on the integrality gap of the SDP relaxation of the Sparsest Cut problem.

Our methods involve Fourier analytic techniques, combined with a breakthrough of Cheeger and Kleiner, along with classical results of Pansu on the differentiability of Lispchitz functions on the Heisenberg group.

We present an $O(\sqrt{\log n} \log \log n)$ upper bound on the $(n-1)$-dimensional volume distortion of $n$-point subsets of a Euclidean space, nearly resolving the main open questions of [Dunagan-Vempala 2001] and [Krauthgamer-Linial-Magen 2004]. The best previous bound was $O(\log n)$ and our bound is nearly tight, as even the $2$-dimensional volume distortion of an $n$-vertex path is $\Omega(\sqrt{\log n})$.

We observe that combining the techniques behind the Sparsest Cut SDP analysis of Arora, Rao, and Vazirani, with the rounding algorithm of Rao and Richa yields an $O(\sqrt{\log n} \log \log n)$-approximation for the minimum linear arrangement problem, improving over the previous bound of $O(\log n)$.

We prove that every \(n\)-point metric space of negative type (and, in particular, every \(n\)-point subset of \(L_1\)) embeds into a Euclidean space with distortion \(O(\sqrt{\log n} \log \log n)\), a result which is tight up to the iterated logarithm factor. As a consequence, we obtain the best known polynomial-time approximation algorithm for the Sparsest Cut problem with general demands. If the demand is supported on a set of size \(k\), we achieve an approximation ratio of \(O(\sqrt{\log k} \log \log k)\).

We develop the algorithmic theory of vertex separators, and its relation to embeddings of certain metric spaces. As a consequence, we obtain an \(O(\sqrt{\log n})\)-approximation for min-ratio vertex cuts in general graphs based on a new SDP relaxation and a tight analysis of its integrality gap.

Our results allow yield algorithms for constructing approximately optimal tree decompositions of graphs. If a graph has treewidth \(k\), we find a tree decomposition of width at most \(O(k \sqrt{\log k})\). If, additionally, the input graph excludes a fixed graph as a minor, we produce a tree decomposition of width \(O(k)\).

Related: A similar method gives improved bounds for the minimum linear arrangement problem.

This paper establishes that a metric space $X$ supports approximate nearest-neighbor queries against any $n$-point subset with at most $\mathrm{poly}(\log n)$ query time if and only if one has certain quantitative estimates on the doubling constant of $n$-point subsets.

We present simple deterministic data structures for maintaining a set of points in a metric space under insertions and deletions, with the ability to make fast nearest-neighbor queries. The running-time of the operations scales with the doubling constant of the underlying metric space.

We establish lower bounds on the polynomial-time approximability of the vertex-connectivity variant of the Survivable Network Design Problem (SNDP) under the assumption that \(\mathsf{NP}\) does not have quasipolynomial-time algorithms. Some related hardness of approximation results are established, e.g., for the edge and vertex-connectivity augmention problems.