3
$\begingroup$

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?

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

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.

$\endgroup$
1
  • $\begingroup$ Well suppose that my problem is an assigment one. Given two sets F and O, with |F| less or equal |O|, and a function cost between the two sets, I want to assign all F to some O minimizing the cost (1 to 1 assignment). I have to design an algorithm that from any given LP-optimal solution of this problem, computes the LPI-optimal solution. The exercise tells me that, for this problem, there is no such integrality gap. Since what you said in your answer, does the request of the exercise have sense? $\endgroup$ Dec 31 '19 at 10:42

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.