<p>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 href="http://dx.doi.org/10.1006/jctb.2000.1989" rel="nofollow">A combinatorial algorithm minimizing submodular functions in strongly polynomial time</a>."  The co-winners (Iwata, Fleischer, and Fujishige) also have "<a href="http://doi.acm.org/10.1145/502090.502096" rel="nofollow">A combinatorial strongly polynomial algorithm for minimizing submodular function</a>."</p>

<p>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 <a href="http://www.opt.math.tu-graz.ac.at/IPCO/" rel="nofollow">IPCO</a> (Integer Programming and Combinatorial Optimization).</p>

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

CC BY-SA 2.5
2011-01-22T04:21:53.613Z
That was the problem that immediately came to my mind as well.
Andrew D. King
CC BY-SA 2.5
2011-01-21T23:27:52.107Z
2011-01-21T23:27:52.107Z
Yoshio Okamoto
<p>With the caveat that I am not quite sure what you're asking about, have you looked at the book on <a href="http://rads.stackoverflow.com/amzn/click/3540653678" rel="nofollow">Approximation Algorithms</a> 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 <a href="http://portal.acm.org/citation.cfm?id=1041683&amp;preflayout=flat" rel="nofollow">local-ratio method</a> 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. </p>

CC BY-SA 2.5
2011-01-21T23:03:20.797Z
The use of primal-dual method can be traced back earlier.  For example, http://cstheory.stackexchange.com/q/3964/2955.
Yoshio Okamoto
CC BY-SA 2.5
2011-01-21T23:05:22.120Z
yes, I didn't mean to imply anything else: merely that for approximation problems, it's been a successful way of generating combinatorial algorithms.
Suresh Venkat
CC BY-SA 2.5
2011-01-21T18:54:36.133Z
2011-01-21T18:54:36.133Z
Suresh Venkat
<p>Last semester, I took a combinatorial optimization course where the reference book was <a href="http://rads.stackoverflow.com/amzn/click/047155894X" rel="nofollow">Combinatorial Optimization</a> 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. </p>

<p>My question is about a general framework on constructing combinatorial algorithms based on LP duality. </p>

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

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

CC BY-SA 2.5
2011-01-21T17:15:37.473Z
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.
Andrew D. King
CC BY-SA 2.5
2011-01-21T18:26:47.750Z
I'm not even quite sure what the question really is.
Suresh Venkat
CC BY-SA 2.5
2011-01-21T21:18:42.877Z
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.
Jeffε
<ds.algorithms><primal-dual>
Necessary and sufficient conditions for the existence of a combinatorial algorithm for a given problem.
Arman
# Necessary and sufficient conditions for the existence of a combinatorial algorithm for a given problem.

(Asked by: username_0 on 2011-01-21)

Last semester, I took a combinatorial optimization course where the reference book was [Combinatorial Optimization](http://rads.stackoverflow.com/amzn/click/047155894X) 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.

**Tags:** ds.algorithms, primal-dual
> **Comments:**
> **username_1**: 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.  
> **username_2**: I'm not even quite sure what the question really is.  
> **username_3**: 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.  

---

## 2 answers

### Answer by username_4 on 2011-01-21. Score: 6

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](http://dx.doi.org/10.1006/jctb.2000.1989)." The co-winners (Iwata, Fleischer, and Fujishige) also have "[A combinatorial strongly polynomial algorithm for minimizing submodular function](http://doi.acm.org/10.1145/502090.502096)."

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](http://www.opt.math.tu-graz.ac.at/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.

> **Comments:**
> **username_1**: That was the problem that immediately came to my mind as well.  

---

### Answer by username_2 on 2011-01-21. Score: 3

With the caveat that I am not quite sure what you're asking about, have you looked at the book on [Approximation Algorithms](http://rads.stackoverflow.com/amzn/click/3540653678) 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](http://portal.acm.org/citation.cfm?id=1041683&preflayout=flat) 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.

> **Comments:**
> **username_4**: The use of primal-dual method can be traced back earlier.  For example, http://cstheory.stackexchange.com/q/3964/2955.  
> **username_2**: yes, I didn't mean to imply anything else: merely that for approximation problems, it's been a successful way of generating combinatorial algorithms.  

---

