<p>See Feige and Jozeph's <a href="https://dl.acm.org/doi/abs/10.1145/2688073.2688101" rel="noreferrer">paper</a> on separation between estimation and approximation.</p>

CC BY-SA 4.0
2021-07-18T03:36:01.083Z
2021-07-18T03:36:01.083Z
Chandra Chekuri
<p>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.</p>
<p>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.</p>
<p>Suppose that I have a Linear Relaxation for a problem and I am able to prove an upper bound of <span class="math-container">$\alpha$</span> on the Integrality Gap for all problem instances. Furthermore, I am able to solve the Linear Relaxation in polynomial time.</p>
<p>Does this imply that there is an <span class="math-container">$\alpha$</span>-approximation for my original combinatorial problem?</p>
<p><strong>Remark</strong>: 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?</p>
<p>Thank you</p>

CC BY-SA 4.0
2021-07-18T02:45:10.973Z
In general there is no such procedure known.
Chandra Chekuri
CC BY-SA 4.0
2021-07-18T02:55:26.040Z
@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?
Karagounis Z
CC BY-SA 4.0
2021-07-18T03:19:28.983Z
This is an example for a minimization problem, that I recently came across https://arxiv.org/abs/2107.07358.
Inuyasha Yagami
CC BY-SA 4.0
2021-07-18T03:25:53.823Z
OP - see this paper for an example. https://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.
Chandra Chekuri
CC BY-SA 4.0
2021-07-18T03:30:13.383Z
@InuyashaYagami having a gap between upper and lower bounds on the integrality gap is not what the OP is asking about.
Chandra Chekuri
CC BY-SA 4.0
2021-07-18T03:41:07.640Z
@ChandraChekuri Oh. Then, I have misunderstood the problem.
Inuyasha Yagami
<co.combinatorics><approximation-algorithms><optimization><linear-programming>
Does an upper bound on the integrality gap imply an approximation algorithm with the same ratio?
Karagounis Z
# Does an upper bound on the integrality gap imply an approximation algorithm with the same ratio?

(Asked by: username_0 on 2021-07-18)

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

**Tags:** co.combinatorics, approximation-algorithms, optimization, linear-programming
> **Comments:**
> **username_1**: In general there is no such procedure known.  
> **username_0**: @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?  
> **username_2**: This is an example for a minimization problem, that I recently came across https://arxiv.org/abs/2107.07358.  
> **username_1**: OP - see this paper for an example. https://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.  
> **username_1**: @InuyashaYagami having a gap between upper and lower bounds on the integrality gap is not what the OP is asking about.  
> **username_2**: @ChandraChekuri Oh. Then, I have misunderstood the problem.  

---

## 1 answers

### Answer by username_1 on 2021-07-18. Score: 5 | Accepted answer

See Feige and Jozeph's [paper](https://dl.acm.org/doi/abs/10.1145/2688073.2688101) on separation between estimation and approximation.


---

