11

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.

Sriram Sankaranarayanan
  • 753
  • 4
  • 18
  • 4
    Note that you can approximate SOCPs with LPs in an efficient way which cannot be done for SDPs. So probably there will be no such a result in theory. In practice it might be that there are problems where it is beneficial to compute a SOCP approximation which gives you better results compared to a LP approximation (or the LP approximation of the SOCP model is considerably larger and takes longer to solve). – JakobS Jun 26 '19 at 15:40
  • http://dx.doi.org/10.1287/moor.26.2.193.10561 for SOCP approximation and https://arxiv.org/abs/1111.0837 for some examples for the SDP case. – JakobS Jun 26 '19 at 15:55
  • Would you mind write out what SOCP stands for? – Renaud M. Jun 26 '19 at 19:25
  • Second Order Cone Program, see http://www.seas.ucla.edu/~vandenbe/publications/socp.pdf or https://link.springer.com/content/pdf/10.1007%2Fs10107-002-0339-5.pdf for a survey of its applications. – Ryan Cory-Wright Jun 26 '19 at 19:35

2 Answers2

4

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.

Ryan Cory-Wright
  • 1,112
  • 1
  • 10
  • 21
  • 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. – Sriram Sankaranarayanan Jun 26 '19 at 18:08
  • 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. – Mark L. Stone Jun 26 '19 at 20:12
  • @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 https://arxiv.org/pdf/1610.04901.pdf. – Ryan Cory-Wright Jun 26 '19 at 21:26
  • 2
    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. – Ryan Cory-Wright Jun 26 '19 at 21:34
3

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.

dourouc05
  • 998
  • 7
  • 17