MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer

Your Answer


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.