10
$\begingroup$

Are there any classes of NP-hard combinatorial optimization problems where Second order cone programs (SOCP) gives a better approximation than linear programs (LP)?

I am looking for results in the flavor of Goemans and Williamson's celebrated result of approximating max-cut using semidefinite programs. But I want to use SOCP instead.

$\endgroup$
3
$\begingroup$

I had heard about comparisons of hierarchies for polynomial optimisations (LP vs. SOCP vs. SDP). For instance, have a look at https://arxiv.org/pdf/1510.06797.pdf.

$\endgroup$
3
$\begingroup$

Interesting question! Unfortunately, Chan et. al. (2013) https://arxiv.org/pdf/1309.0563.pdf have shown that any polynomially sized LP relaxation of max-cut has an integrality gap of $\frac{1}{2}$ in the worst-case. Since, as pointed out in the comments, Ben-Tal and Nemirovski have shown that SOCPs can be approximated by polynomially-sized LPs, polynomially-sized SOCP relaxations of max-cut therefore have an integrality gap of $\frac{1}{2}$ in the worst-case.

$\endgroup$
  • $\begingroup$ Thank you. But I was not thinking of only max-cut. Max cut/GW result was just an example. But I agree, Ben-Tal and Nemirovski have answered the question. $\endgroup$ – Sriram Sankaranarayanan Jun 26 at 18:08
  • $\begingroup$ Not following your last sentence. Polynomial-sized LP relaxation of max cut has worst case 1/2 integrality gap. But is it possible that SOCP relaxation not involving (further) Polynomial-sized LP relaxation of SOCP does better? I.e., why does Can et al result imply anything about SOCP relaxation, rather just what the situation is for LP relaxation? Not the same thing, but consider that SOCPs can be modeled exactly and solved as linear SDPs, but you can't apply worst case results for general linear SDP to SOCP just because SOCP can be handled as linear SDP. $\endgroup$ – Mark L. Stone Jun 26 at 20:12
  • $\begingroup$ @MarkL.Stone because while you can reduce SOCPs to polynomially-sized LPs and vice versa, you can't reduce an SDP to a polynomially sized SOCP in general, as recently proven by Fawazi in arxiv.org/pdf/1610.04901.pdf. $\endgroup$ – Ryan Cory-Wright Jun 26 at 21:26
  • 2
    $\begingroup$ To answer your question: if we had a strictly better approximation for SOCPs then we could apply the BTN01 result to the SOCP and obtain a polynomial-sized LP which also had this guarantee, which would contradict the Chan et. al. result. Because SDPs are more expressive than SOCPs (in a way which SOCPs aren't w.r.t. LPs), the same proof by contradiction doesn't work with reducing SOCP to SDP. $\endgroup$ – Ryan Cory-Wright Jun 26 at 21:34

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.