0
$\begingroup$

Often, we can model combinatorial optimization problems with an Integer Program. Then there is an associated Linear Relaxation which drops the integrality constraints on the variables.

Let's say we are dealing with a maximization problem. Then the Integrality Gap of a Linear Relaxation is the maximum ratio between the optimum LP solution and the optimum IP solution.

Suppose that I have a Linear Relaxation for a problem and I am able to prove an upper bound of $\alpha$ on the Integrality Gap for all problem instances. Furthermore, I am able to solve the Linear Relaxation in polynomial time.

Does this imply that there is an $\alpha$-approximation for my original combinatorial problem?

Remark: Often the proof of the upper bound on the integrality gap involves giving an explicit rounding technique which can then be converted into an approximation algorithm. But my question is, is there a general procedure to go from a bounded integrality gap to an approximate solution to the integer program?

Thank you

$\endgroup$
6
  • $\begingroup$ In general there is no such procedure known. $\endgroup$ Jul 18 at 2:45
  • $\begingroup$ @ChandraChekuri Are there any examples where an integrality gap upper bound is known, but we don't have an algorithm with a matching approximation ratio? $\endgroup$ Jul 18 at 2:55
  • $\begingroup$ This is an example for a minimization problem, that I recently came across arxiv.org/abs/2107.07358. $\endgroup$ Jul 18 at 3:19
  • $\begingroup$ OP - see this paper for an example. dl.acm.org/doi/10.1145/3070694 I am not sure about the current status of the problem but in general one may be able to prove an upper bound on the integrality gap via an inefficient algorithm. $\endgroup$ Jul 18 at 3:25
  • 1
    $\begingroup$ @InuyashaYagami having a gap between upper and lower bounds on the integrality gap is not what the OP is asking about. $\endgroup$ Jul 18 at 3:30
5
$\begingroup$

See Feige and Jozeph's paper on separation between estimation and approximation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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