Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)|$?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.