Are there results that bound the asymmetry of the duality gap of an integer program? That is to say, if the difference between the LP solution and the IP (primal) solution is $a$, is there a function $f$ so that difference between the LP solution and the IP dual solution is $< |f(a)|$?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
