On Approximation Algorithms for Minimum Linear Arrangement
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 (no previous knowledge of which will be necessary). 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).
This is joint work with Moses Charikar of Princeton and Satish Rao of Berkeley.
|
Dr. Howard Karloff received his PhD in computer science from the University of California at Berkeley. Before joining AT&T Labs, he was Assistant Professor at University of Chicago and Associate and Full Professor at Georgia Institute of Technology. He serves as an editor for Journal of Algorithms and on the NSF Panel for Theory of Computation, was in the technical committee at the flagship conference Foundation of Theoretical Computer Science (FOCS) and the chair of the Symposium of Discrete Algorithms (SODA). He is the author of about 40 journal articles, including two in the Journal of the ACM, and the book "Linear Programming". His research interests span theoretical computer science, with an emphasis on algorithms. |