<p>The $L_1$ problem with $d_v=1$ for all $v$ is <strong><em>a variant of</em></strong> the classical NP-hard <a href="http://www.nada.kth.se/~viggo/wwwcompendium/node55.html#4205" rel="nofollow">minimum linear arrangement</a> problem.   <a href="http://www-math.mit.edu/~hajiagha/procversion3.pdf" rel="nofollow">Charikar et al [SODA 2006]</a> and independently <a href="http://www.cs.washington.edu/homes/jrl/papers/feige-lee.pdf" rel="nofollow">Feige and Lee [IPL 2007]</a> described polynomial-time $O(\sqrt{\log n} \log \log n)$-approximation algorithms via semidefinite programming.  <a href="http://cs.nyu.edu/~khot/papers/usc-mla.pdf" rel="nofollow">Devanur et al [STOC 2006]</a> proved an $\Omega(\log\log n)$ integrality gap for the semidefinite relaxation.</p>

CC BY-SA 3.0
2012-04-23T18:33:40.470Z
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.
Tahw Pu
CC BY-SA 3.0
2012-04-23T20:37:22.620Z
Oops, my mistake!  Edited to clarify.
Jeffε
CC BY-SA 3.0
2012-04-22T16:45:11.300Z
2012-04-23T20:34:01.547Z
2012-04-23T20:34:01.547Z
Jeffε
<p>Suppose we have a multigraph with vertex set $V$ where for each $v \in V$, $d_v &gt; 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. </p>

<p>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.</p>

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

<cg.comp-geom><optimization>
Minimum ($\ell_1$ or $\ell_2$) norm of sum of edge length in multigraph over linear ordering of vertices
Tahw Pu
# Minimum ($\ell_1$ or $\ell_2$) norm of sum of edge length in multigraph over linear ordering of vertices

(Asked by: username_0 on 2012-04-20)

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?

**Tags:** cg.comp-geom, optimization

---

## 1 answers

### Answer by username_1 on 2012-04-22. Score: 5 | Accepted answer

The $L\_1$ problem with $d\_v=1$ for all $v$ is ***a variant of*** the classical NP-hard [minimum linear arrangement](http://www.nada.kth.se/~viggo/wwwcompendium/node55.html#4205) problem. [Charikar et al [SODA 2006]](http://www-math.mit.edu/~hajiagha/procversion3.pdf) and independently [Feige and Lee [IPL 2007]](http://www.cs.washington.edu/homes/jrl/papers/feige-lee.pdf) described polynomial-time $O(\sqrt{\log n} \log \log n)$-approximation algorithms via semidefinite programming. [Devanur et al [STOC 2006]](http://cs.nyu.edu/~khot/papers/usc-mla.pdf) proved an $\Omega(\log\log n)$ integrality gap for the semidefinite relaxation.

> **Comments:**
> **username_0**: 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.  
> **username_1**: Oops, my mistake!  Edited to clarify.  

---

