<p>Well, there are cases where LP gives you no useful information. Consider a graph $G$ with $n$ vertices, and the problem of finding a maximum independent set in $G$. The LP gives you a solution of value at least $n/2$ (give every vertex a value of $1/2$). But the optimal independent set might be of size between $1$ and $n$.</p>

<p>On the other hand, the greedy algorithm does give useful results in some cases. For example, if the number of edges is $m \ll n^2$, then the greedy algorithm would give you an independent set of size $\Omega(n^2/m)$ (always pick the vertex that has the smallest numbeer of neighbors).</p>

CC BY-SA 3.0
2015-06-21T07:45:03.640Z
2015-06-21T07:45:03.640Z
Sariel Har-Peled
<p>I wanted to know whether Greedy approximation algorithms can outperform LP relaxation and rounding based algorithms. Specifically, can it beat the integrality gap of a 'reasonable' LP relaxation, (e.g. the natural relaxation of the ILP by relaxing variables $x_i\in\{1,0\}$ to $x\geq 0$). </p>

<p>For an example, if we consider the Setcover problem with universe set $U$ s.t. $|U|=n$ with max frequency of an element $f$, the greedy algorithm gives an $O(\mathrm{log}~n)$ approximation. Whereas LP relaxation can give an $f$ approximation with deterministic rounding. But we know that the integrality gap is $\Omega(\mathrm{log}~n)$ for the general LP formulation. Indeed through a randomized rounding technique we can achieve a $O(\mathrm{log}~n)$ approximation w.h.p. So the greedy is almost as good as the LP relaxation.</p>

<p>Does anyone know of an instance of NP Hard problem having approximations using greedy algorithm which is better than the integrality gap? Please point out the references if known. It will be great if the problem is well studied. </p>

CC BY-SA 3.0
2015-06-24T05:29:41.190Z
How about the 2-approximation alg. for metric k-clustering?  https://en.wikipedia.org/wiki/Metric_k-center.  I don't know of any LP for that one.
Neal Young
CC BY-SA 3.0
2015-06-24T08:44:38.660Z
Specifically, I wanted to see if any greedy algorithm can beat the integrality gap for the general relaxation from ILP to LP. The mentioned reference shows greedy algorithm performs well but it does not clarify the above point.
Soumya Basu
CC BY-SA 3.0
2015-06-25T15:39:13.233Z
OK actually for $k$-center isn't there an LP relaxation, similar to the k-medians LP?  Namely $\min\{ r : \sum_j y_j \le k; \forall i.~\sum_{j} x_{ij} = 1; \forall i,j.~0 \le x_{ij} \le r/d(i,j), x_{ij} \le y_j\}$ where variables $x_{ij}$ and $y_j$ are 0/1 and $r$ is fractional.  I think integrality gap can be large: take $n\ge k+1$ points all at distance 1 from each other. Optimal integer solution has $r=1$.  Fractional solution with each $x_{ij} = y_j = 1/n$ has $r=1/n$.
Neal Young
CC BY-SA 3.0
2015-06-25T15:44:51.610Z
Also, the notion of "the" LP, and "the" LP relaxation is, formally, not very well-defined.  For a given LP, you can relax the integrality constraints, but if you add enough additional linear constraints in your LP (e.g. cutting planes, etc), the polytope of the relaxed LP will have only integer vertices, and integrality gap will always be 1.
Neal Young
<convex-optimization><combinatorics><integrality-gap>
Greedy vs LP Approximation
Soumya Basu
# Greedy vs LP Approximation

(Asked by: username_0 on 2015-06-20)

I wanted to know whether Greedy approximation algorithms can outperform LP relaxation and rounding based algorithms. Specifically, can it beat the integrality gap of a 'reasonable' LP relaxation, (e.g. the natural relaxation of the ILP by relaxing variables $x\_i\in\{1,0\}$ to $x\geq 0$).

For an example, if we consider the Setcover problem with universe set $U$ s.t. $|U|=n$ with max frequency of an element $f$, the greedy algorithm gives an $O(\mathrm{log}~n)$ approximation. Whereas LP relaxation can give an $f$ approximation with deterministic rounding. But we know that the integrality gap is $\Omega(\mathrm{log}~n)$ for the general LP formulation. Indeed through a randomized rounding technique we can achieve a $O(\mathrm{log}~n)$ approximation w.h.p. So the greedy is almost as good as the LP relaxation.

Does anyone know of an instance of NP Hard problem having approximations using greedy algorithm which is better than the integrality gap? Please point out the references if known. It will be great if the problem is well studied.

**Tags:** convex-optimization, combinatorics, integrality-gap
> **Comments:**
> **username_1**: How about the 2-approximation alg. for metric k-clustering?  https://en.wikipedia.org/wiki/Metric_k-center.  I don't know of any LP for that one.  
> **username_0**: Specifically, I wanted to see if any greedy algorithm can beat the integrality gap for the general relaxation from ILP to LP. The mentioned reference shows greedy algorithm performs well but it does not clarify the above point.  
> **username_1**: OK actually for $k$-center isn't there an LP relaxation, similar to the k-medians LP?  Namely $\min\{ r : \sum_j y_j \le k; \forall i.~\sum_{j} x_{ij} = 1; \forall i,j.~0 \le x_{ij} \le r/d(i,j), x_{ij} \le y_j\}$ where variables $x_{ij}$ and $y_j$ are 0/1 and $r$ is fractional.  I think integrality gap can be large: take $n\ge k+1$ points all at distance 1 from each other. Optimal integer solution has $r=1$.  Fractional solution with each $x_{ij} = y_j = 1/n$ has $r=1/n$.  
> **username_1**: Also, the notion of "the" LP, and "the" LP relaxation is, formally, not very well-defined.  For a given LP, you can relax the integrality constraints, but if you add enough additional linear constraints in your LP (e.g. cutting planes, etc), the polytope of the relaxed LP will have only integer vertices, and integrality gap will always be 1.  

---

## 1 answers

### Answer by username_2 on 2015-06-21. Score: 6 | Accepted answer

Well, there are cases where LP gives you no useful information. Consider a graph $G$ with $n$ vertices, and the problem of finding a maximum independent set in $G$. The LP gives you a solution of value at least $n/2$ (give every vertex a value of $1/2$). But the optimal independent set might be of size between $1$ and $n$.

On the other hand, the greedy algorithm does give useful results in some cases. For example, if the number of edges is $m \ll n^2$, then the greedy algorithm would give you an independent set of size $\Omega(n^2/m)$ (always pick the vertex that has the smallest numbeer of neighbors).


---

