Minimum ($\ell_1$ or $\ell_2$) norm of sum of edge length in multigraph over linear ordering of vertices

Question

Suppose we have a multigraph with vertex set $V$ where for each $v \in V$, $d_v > 0$ is the diameter of the vertex. We want to put a linear ordering on the set of vertices such it minimizes ($L_1$ or $L_2$ norm of) the sum of edge length when vertices are drawn on a line (according to that linear ordering). The vertices are non overlapping circles with diameter $d_v$ and each edge can start anywhere in the respective circles as long as it is confined to the boundary of the given circles and all the other edges start at the same position.

A physical interpretation of this would be that there are N balls connected with ropes (the rope can start anywhere inside the ball but every rope connected to that same ball must start from the same place too) We want to place the balls on a line such that the total length of the ropes used in minimized.

Is there any efficient algorithm known for this type of problem? How about approximation algorithms?

Answer 1

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.