2
$\begingroup$

Many network optimization algorithms, including shortest path, push-relabel, augmenting path, etc, actually have an interpretation in terms of linear programming.

A famous application of semidefinite programming is the max-cut approximation. Does this optimization algorithm, or any other on networks, have a network interpretation, a la augmenting path?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

I think what you are actually after is the elusive combinatorial interpretation of SDPs. While this is in general a rather tricky issue, a very nice piece of work that is a good starting point, and brings SDPs closer to combinatorial algorithms is:

A combinatorial primal-dual approach to semidefinite programs by S. Arora and S. Kale.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .