<p>Yes: the dual is a multicommodity flow problem which can be solved using the Garg-Koenemann algorithm <a href="http://dx.doi.org/10.1137/S0097539704446232" rel="nofollow">http://dx.doi.org/10.1137/S0097539704446232</a>.</p>

CC BY-SA 3.0
2011-07-12T06:23:28.020Z
I can not download the article, but what I don't like is a word "approximate" in the abstract.
ilyaraz
CC BY-SA 3.0
2011-07-12T07:38:41.853Z
Google for the title: it's in citeseer. All combinatorial algorithms of this style give a $1 +\epsilon$ approximation in time that depends on $\epsilon$ as $\frac{1}{\epsilon^2}$. The usual argument is that if your goal is to compute the $O(\log n)$ approximation, then the $1+\epsilon$ factor is acceptable in comparison. I believe if you want $\log \frac{1}{\epsilon}$ dependence, then your only choice is a "real" LP algorithm. BTW, your LP can be written with $O(n^3)$ constraints, so you can use interior point methods.
Sasho Nikolov
CC BY-SA 3.0
2011-07-12T06:07:29.590Z
2011-07-12T06:07:29.590Z
Sasho Nikolov
<p>This question is motivated by the Leighton-Rao relaxation for SPARSEST-CUT.</p>

<p>Suppose one wants to find a non-trivial semimetric over an $n$-point space that minimizes a certain linear functional. More formally:</p>

<ul>
<li>minimize $\sum_{ij = 1}^n c_{ij} d_{ij}$</li>
<li>where $d$ is a semimetric over $\{1, 2, \ldots, n\}$</li>
<li>and $\sum_{ij = 1}^n d_{ij} = 1$</li>
</ul>

<p>Of course it is a linear program that can be solved in polynomial time using ellipsoid method. But what I would like to know is if there are any combinatorial algorithms for this optimization problem. I suspect that the answer is 'no' since the problem looks pretty general to be solved combinatorially, but who knows...</p>

<ds.algorithms><optimization><linear-programming><metrics>
Combinatorial algorithm for optimization over semimetric polytope
ilyaraz
# Combinatorial algorithm for optimization over semimetric polytope

(Asked by: username_0 on 2011-07-11)

This question is motivated by the Leighton-Rao relaxation for SPARSEST-CUT.

Suppose one wants to find a non-trivial semimetric over an $n$-point space that minimizes a certain linear functional. More formally:

* minimize $\sum\_{ij = 1}^n c\_{ij} d\_{ij}$
* where $d$ is a semimetric over $\{1, 2, \ldots, n\}$
* and $\sum\_{ij = 1}^n d\_{ij} = 1$

Of course it is a linear program that can be solved in polynomial time using ellipsoid method. But what I would like to know is if there are any combinatorial algorithms for this optimization problem. I suspect that the answer is 'no' since the problem looks pretty general to be solved combinatorially, but who knows...

**Tags:** ds.algorithms, optimization, linear-programming, metrics

---

## 1 answers

### Answer by username_1 on 2011-07-12. Score: 4 | Accepted answer

Yes: the dual is a multicommodity flow problem which can be solved using the Garg-Koenemann algorithm <http://dx.doi.org/10.1137/S0097539704446232>.

> **Comments:**
> **username_0**: I can not download the article, but what I don't like is a word "approximate" in the abstract.  
> **username_1**: Google for the title: it's in citeseer. All combinatorial algorithms of this style give a $1 +\epsilon$ approximation in time that depends on $\epsilon$ as $\frac{1}{\epsilon^2}$. The usual argument is that if your goal is to compute the $O(\log n)$ approximation, then the $1+\epsilon$ factor is acceptable in comparison. I believe if you want $\log \frac{1}{\epsilon}$ dependence, then your only choice is a "real" LP algorithm. BTW, your LP can be written with $O(n^3)$ constraints, so you can use interior point methods.  

---

