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.
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ 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 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. $\endgroup$– D.W.Commented Jul 1, 2015 at 18:09
-
$\begingroup$ 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. $\endgroup$– user1105Commented Jul 2, 2015 at 15:49
-
$\begingroup$ Also, aren't these questions equally vague and generic as my question. Question 1 and question 2. $\endgroup$– user1105Commented Jul 2, 2015 at 18:33
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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
$\begingroup$
$\endgroup$
Some of the linear programs which comes to my mind are
- George Dantzig’s linear program for Traveling Salesman Problem. You can find a nice description of the result here.
- 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.
I'm sure there are a lot more of them out there.