Return to Revisions

The $L_1$ problem with $d_v=1$ for all $v$ is a variant of the classical NP-hard minimum linear arrangement problem. Charikar et al [SODA 2006] and independently Feige and Lee [IPL 2007] described polynomial-time $O(\sqrt{\log n} \log \log n)$-approximation algorithms via semidefinite programming. Devanur et al [STOC 2006] proved an $\Omega(\log\log n)$ integrality gap for the semidefinite relaxation.