<p>The relaxation of Calinescu, Karloff and Rabani for the undirected Multiway Cut problem is one my favorites. Had a big influence on subsequent work.
<a href="http://www.sciencedirect.com/science/article/pii/S0022000099916872">http://www.sciencedirect.com/science/article/pii/S0022000099916872</a></p>

CC BY-SA 3.0
2015-07-04T20:33:32.590Z
2015-07-04T20:33:32.590Z
Chandra Chekuri
<p>Some of the linear programs which comes to my mind are</p>

<ol>
<li>George Dantzig’s linear program for Traveling Salesman Problem. You can find a nice description of the result <a href="http://www.sciencedirect.com/science/article/pii/S1572528607000412" rel="nofollow">here</a>.</li>
<li>Flow based Linear program for Capacitated Facility Location Problem. This was a FOCS2014 paper which settled the long standing open problem of whether there is a linear program for this problem with constant integrality gap. You can find the paper <a href="http://arxiv.org/abs/1407.3263" rel="nofollow">here</a>.</li>
</ol>

<p>I'm sure there are a lot more of them out there.</p>

CC BY-SA 3.0
2015-07-01T07:34:32.630Z
2015-07-02T14:19:46.017Z
2015-07-02T14:19:46.017Z
user1105
<p>What are some known ingenious linear programs that have been developed for tackling hard combinatorial optimization problems, especially any linear programs which had helped in getting good approximation algorithms for long standing open questions related to NP-hard optimization problems.</p>

CC BY-SA 3.0
2015-07-01T18:09:54.600Z
I'm afraid this question is not suitable for this site.  This is not a discussion forum; it is for narrowly-focused, objectively answerable technical questions.  See http://cstheory.stackexchange.com/help/dont-ask.  In particular, note this part: "If your motivation for asking the question is “I would like to participate in a discussion about ______”, then you should not be asking here."  The question is currently too broad; and a call for discussion is not suitable here, as our format is not well-suited to discussion.
D.W.
CC BY-SA 3.0
2015-07-02T15:49:16.513Z
I have narrowed it down to "novel LP's used in approximation algorithm", I just need reference to some nice LP's which helped in tackling hard problems and led to good approximation algorithms for them.
user1105
CC BY-SA 3.0
2015-07-02T18:33:39.523Z
Also, aren't these questions equally vague and generic as my question. [Question 1](http://cstheory.stackexchange.com/questions/1168/what-papers-should-everyone-read/1169#1169) and [question 2](http://cstheory.stackexchange.com/questions/4806/how-do-you-get-a-physical-intuition-for-results-in-tcs/4813#4813).
user1105
<co.combinatorics><approximation-algorithms><optimization><linear-programming>
What are some of the most ingenious linear programs developed for tackling hard combinatorial problems?
user1105
# What are some of the most ingenious linear programs developed for tackling hard combinatorial problems?

(Asked by: username_0 on 2015-07-01)

What are some known ingenious linear programs that have been developed for tackling hard combinatorial optimization problems, especially any linear programs which had helped in getting good approximation algorithms for long standing open questions related to NP-hard optimization problems.

**Tags:** co.combinatorics, approximation-algorithms, optimization, linear-programming
> **Comments:**
> **username_1**: I'm afraid this question is not suitable for this site.  This is not a discussion forum; it is for narrowly-focused, objectively answerable technical questions.  See http://cstheory.stackexchange.com/help/dont-ask.  In particular, note this part: "If your motivation for asking the question is “I would like to participate in a discussion about ______”, then you should not be asking here."  The question is currently too broad; and a call for discussion is not suitable here, as our format is not well-suited to discussion.  
> **username_0**: I have narrowed it down to "novel LP's used in approximation algorithm", I just need reference to some nice LP's which helped in tackling hard problems and led to good approximation algorithms for them.  
> **username_0**: Also, aren't these questions equally vague and generic as my question. [Question 1](http://cstheory.stackexchange.com/questions/1168/what-papers-should-everyone-read/1169#1169) and [question 2](http://cstheory.stackexchange.com/questions/4806/how-do-you-get-a-physical-intuition-for-results-in-tcs/4813#4813).  

---

## 2 answers

### Answer by username_2 on 2015-07-04. Score: 6

The relaxation of Calinescu, Karloff and Rabani for the undirected Multiway Cut problem is one my favorites. Had a big influence on subsequent work.
<http://www.sciencedirect.com/science/article/pii/S0022000099916872>


---

### Answer by username_0 on 2015-07-01. Score: 5

Some of the linear programs which comes to my mind are

1. George Dantzig’s linear program for Traveling Salesman Problem. You can find a nice description of the result [here](http://www.sciencedirect.com/science/article/pii/S1572528607000412).
2. Flow based Linear program for Capacitated Facility Location Problem. This was a FOCS2014 paper which settled the long standing open problem of whether there is a linear program for this problem with constant integrality gap. You can find the paper [here](http://arxiv.org/abs/1407.3263).

I'm sure there are a lot more of them out there.


---

