# Combinatorial algorithm for optimization over semimetric polytope

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

• 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. Jul 12, 2011 at 7:38