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

Improve this question
$\endgroup$
6
  • $\begingroup$ In general there is no such procedure known. $\endgroup$
    – Chandra Chekuri
    Jul 18, 2021 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$
    – Karagounis Z
    Jul 18, 2021 at 2:55
  • $\begingroup$ This is an example for a minimization problem, that I recently came across arxiv.org/abs/2107.07358. $\endgroup$
    – Inuyasha Yagami
    Jul 18, 2021 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$
    – Chandra Chekuri
    Jul 18, 2021 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$
    – Chandra Chekuri
    Jul 18, 2021 at 3:30

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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