UGC conjecture pretty much says the gaps obtained currently with SDPs are the best we can hope for. Packing and covering problems are typically cast as LPs and we get gaps in these. Are the gaps in these problems explainable by UGC or there any reverse connections?

  • $\begingroup$ Well, there are certainly connections between UGC and inapproximability results for packing/covering LPs. e.g. scholar.google.com/… . This doesn't directly establish integrality gaps, but it is often the case that integrality gaps of well-known LPs correspond to best poly-time approximation ratios, so there is a soft connection at least. Perhaps you could edit to clarify what kind of connection you are looking for. $\endgroup$ – Neal Young Feb 14 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.