# Are there intuitive/classically algorithmic analogues to Semidefinite programs on networks?

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?

-

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.

-