1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ How about the 2-approximation alg. for metric k-clustering? en.wikipedia.org/wiki/Metric_k-center. I don't know of any LP for that one. $\endgroup$
    – Neal Young
    Jun 24 '15 at 5:29
  • $\begingroup$ 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. $\endgroup$
    – Soumya Basu
    Jun 24 '15 at 8:44
  • $\begingroup$ 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$. $\endgroup$
    – Neal Young
    Jun 25 '15 at 15:39
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Jun 25 '15 at 15:44
6
$\begingroup$

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).

Improve this answer
$\endgroup$

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.