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?


1 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.

  • $\begingroup$ This is not exactly the minimum linear arrangement problem for $d_v = 1$ as the edges can start anywhere within the vertex as opposed to the center, but you pointed out all the references that I needed. Thanks. $\endgroup$
    – Tahw Pu
    Apr 23, 2012 at 18:33
  • $\begingroup$ Oops, my mistake! Edited to clarify. $\endgroup$
    – Jeffε
    Apr 23, 2012 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.