3
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I can not download the article, but what I don't like is a word "approximate" in the abstract. $\endgroup$
    – ilyaraz
    Jul 12, 2011 at 6:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Jul 12, 2011 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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