This book is primarily a textbook introduction to various areas of discrete geometry. In each
area, it explains several key results and methods, in an accessible and concrete manner. It …

In this paper, we establish max-flow min-cut theorems for several important classes of
multicommodity flow problems. In particular, we show that for any n-node multicommodity …

In this paper, we show that any n point metric space can be embedded into a distribution
over dominating tree metrics such that the expected stretch of any edge is O (log n). This …

A basic fact in spectral graph theory is that the number of connected components in an
undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of …

We consider the following general correlation-clustering problem [N. Bansal, A. Blum, S.
Chawla, Correlation clustering, in: Proc. 43rd Annu. IEEE Symp. on Foundations of …

We develop the algorithmic theory of vertex separators, and its relation to the embeddings of
certain metric spaces. Unlike in the edge case, we show that embeddings into L1 (and even …

We introduce a new framework for designing fixed-parameter algorithms with
subexponential running time---2 O (√ k) n O (1). Our results apply to a broad family of graph …

Consider the multicommodity flow problem in which the object is to maximize the sum of
commodities routed. We prove the following approximate max-flow min-multicut theorem …

A principle task in parallel and distributed systems is to reduce the communication load in
the interconnection network, as this is usually the major bottleneck for the performance of …

Due to the fact that no NP-complete problem can be solved in polynomial time (unless P=
NP), many approximability results (both positive and negative) of NP-hard optimization …