Abstract:

We study Minimum Linear Arrangement (MLA), the problem of placing the n
vertices of a graph onto {1,2,3,...,n} so as to minimize the sum of the edge
lengths.  Until the appearance of Arora, Rao, and Vazirani's groundbreaking
work on Sparsest Cut, the best known approximation ratio for MLA was O(log
n), achieved by Rao and Richa, who improved on a O((log n)(log log n))
approximation algorithm of Even, Naor, Rao, and Schieber.

We show how to use the main lemma of Arora, Rao, and Vazirani, together with
the decomposition techniques of Rao and Richa, to improve the approximation
ratio of MLA to O((sqrt(log n))log log n).
The best part is, no previous knowledge of [ARV] will be necessary.

This is joint work with Moses Charikar of Princeton and Satish Rao of
Berkeley.