patternMinor
Integrality gap and LP-rounding
Viewed 0 times
andintegralitygaprounding
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#119023, answer score: 3
Revisions (0)
No revisions yet.