Saturday, 1 August 2009

linear programming - Symmetry of the integer gap

Here is an example showing this is impossible, I think. The integrality gap for "independent set" can be up to $n/2$ on a graph with $n$ vertices. But its dual is the naive LP relaxation of edge cover on the same graph; you can show a constant integrality gap upper bound for this by standard methods (and Ojas Parekh proves in his thesis that the best possible bound is 4/3).



This example behaves similarly if you care about the approximability, I have worked on a paper which motivated my example above.

No comments:

Post a Comment