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