# Integrality gap and LP-rounding

I have a doubt about integrality gap. If I know that there is no integrality gap for a given problem, i.e.:

$$\frac{\mathrm{OPT}(\mathrm{ILP})}{\mathrm{OPT}(\mathrm{LP})} = 1 \text{ (right?)},$$ then, does it have sense to do an approximation-algorithm with LP-rounding? I mean, by definition of $$\alpha$$-approximation, I know that this is true for an algorithm, in case of minimization problem, that:

$$\mathrm{SOL} \le \alpha \mathrm{OPT}.$$

But since I want to do an approximation with LP-rounding, isn't $$\mathrm{SOL}$$ equal to $$\mathrm{OPT}(\mathrm{ILP})$$? This will mean that $$\alpha = 1$$ (?).

So, if I can design an approximation-algorithm for this given problem, what is the best approximation factor that I can get, given there is no integrality gap?

• The best you could hope for is a 1-approximation, that is, an algorithm which finds an optimal solution. Dec 31 '19 at 9:29

For first question: No, it doesn't make sense. If there is no ratio between OPT(ILP) and OPT(LP-relax) (i.e. integrality gap is 1) which is very rarely to happen (only happen with problem that is in $$P$$), then this means that you reach the optimal solution for this problem. It is known that LP-relax cannot give the optimal solution for a problem (except for problems in P as I said), and this is why we define integrality gap to see how far it from the optimal solution of the problem (or optimal solution of the ILP).
For second question: Yes, it is true, $$\alpha = 1$$.
For third question: if you design an approximation algorithm for a given a problem, then I believe you are talking about problem that lies in NP-hard. Then the best factor you hope for max/min problem is 1 (Note that max problem has ratios between [0-1], whereas min problem has ratios between [1,$$\infty$$)). In reality, all NP-hard problems cannot get a polynomial approximation algorithm with ratio 1 unless P=NP "since ratio 1-approximation algorithm is the same as exact algorithm". So, it should be closer to 1 for both max/min problems but not equal 1.