Minimum ($\ell_1$ or $\ell_2$) norm of sum of edge length in multigraph over linear ordering of vertices
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.