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