2
$\begingroup$

Last semester, I took a combinatorial optimization course where the reference book was Combinatorial Optimization by William J. Cook et al. It was very interesting for me to see the relationship between some great algorithms (like disjktra's shortest path algorithm, edmonds' maximum matching algorithm ...) and LP duality.

My question is about a general framework on constructing combinatorial algorithms based on LP duality.

For a given problem what are the necessary and sufficient conditions for the existence of such algorithms. I think duality gap should be the first necessary condition and to have a totally unimodal matrix could be sufficient.

Maybe the answer is written in that book and I should read it again carefully.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Before you answer this question you have to decide whether or not you can come up with a sufficiently general framework for defining a combinatorial algorithm. $\endgroup$
    – Andrew D. King
    Jan 21, 2011 at 17:15
  • 1
    $\begingroup$ I'm not even quite sure what the question really is. $\endgroup$
    – Suresh Venkat
    Jan 21, 2011 at 18:26
  • 2
    $\begingroup$ I have to agree with Suresh; there is no standard definition for "combinatorial algorithm". Do you mean "smells like LP", or do you mean "no games with bits, even in the analysis" (like Dijkstra's algorithm), or something else? Keep in mind that there is no polynomial-time combinatorial algorithm for LP., according to the second definition. $\endgroup$
    – Jeffε
    Jan 21, 2011 at 21:18

2 Answers 2

Reset to default
6
$\begingroup$

Some people in combinatorial optimization use the word "combinatorial algorithm" to mean "algorithm without using ellipsoid method (or interior-point methods)." For example, Schrijver's Fulkerson-prize-winning paper has a title "A combinatorial algorithm minimizing submodular functions in strongly polynomial time." The co-winners (Iwata, Fleischer, and Fujishige) also have "A combinatorial strongly polynomial algorithm for minimizing submodular function."

As far as I see the field of combinatorial optimization, people there actually try to give an answer to the posed question, and still struggle. Cunningham's survey "Matching, matroids, and extensions" (Mathematical Programming B91 (2002) 515-542) is a bit old by now, but you can see how generalizations of Edmonds' blossom algorithm and concepts on matroid lead to combinatorial polynomial-time algorithms for other problems. Please note that the field has been advanced since the survey, and good sources are probably some papers from IPCO (Integer Programming and Combinatorial Optimization).

I would like to point out that an big open problem is to find a combinatorial algorithm for the maximum independent set problem for perfect graphs running in strongly polynomial time.

Improve this answer
$\endgroup$
1
  • $\begingroup$ That was the problem that immediately came to my mind as well. $\endgroup$
    – Andrew D. King
    Jan 22, 2011 at 4:21
3
$\begingroup$

With the caveat that I am not quite sure what you're asking about, have you looked at the book on Approximation Algorithms by Vijay Vazirani ? There are two techniques (that are quite related to each other) for using LPs to design combinatorial algorithms. One is of course the primal-dual method that Vijay has propounded for a while, and is explained nicely in the book. Another is the local-ratio method developed by Reuven Bar-Yehuda and others, which it tuns out is also closely related to primal-dual methods. Another perspective that's proven to be useful is the 'pricing' model, which has a more game-theoretic flavor but is also another way of navigating primals and duals in a combinatorial manner.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The use of primal-dual method can be traced back earlier. For example, cstheory.stackexchange.com/q/3964/2955. $\endgroup$
    – Yoshio Okamoto
    Jan 21, 2011 at 23:03
  • $\begingroup$ yes, I didn't mean to imply anything else: merely that for approximation problems, it's been a successful way of generating combinatorial algorithms. $\endgroup$
    – Suresh Venkat
    Jan 21, 2011 at 23:05

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.