Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Affine reductions for LPs and SDPs

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

We define a reduction mechanism for LP and SDP formulations that degrades approximation factors in a controlled fashion. Our reduction mechanism is a minor restriction of classical hardness reductions requiring an additional independence assumption and it allows for reusing many hardness reductions that have been used to show inapproximability in the context of PCP theorems. As a consequence we establish strong linear programming inapproximability (for LPs with a polynomial number of constraints) for many problems. In particular we obtain a \(\frac{3}{2}-\varepsilon \) inapproximability for answering an open question in Chan et al. (Proceedings of FOCS, pp. 350–359, 2013, https://doi.org/10.1109/FOCS.2013.45) and prove an inapproximability factor of \(\frac{1}{2}+\varepsilon \) for bounded degree . In the case of SDPs, we obtain inapproximability results for these problems relative to the SDP-inapproximability of \({\textsf {MaxCUT}}_{}\). Moreover, using our reduction framework we are able to reproduce various results for CSPs from Chan et al. (Proceedings of FOCS, pp. 350–359, 2013, https://doi.org/10.1109/FOCS.2013.45) via simple reductions from Max-\(2\)-XOR.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Agarwal, A., Charikar, M., Makarychev, K., Makarychev, Y.: \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems. In: Proceedings of STOC, pp. 573–581. ACM (2005)

  2. Austrin, P., Khot, S., Safra, M.: Inapproximability of vertex cover and independent set in bounded degree graphs. In: Computational Complexity, CCC, pp. 74–80. IEEE (2009)

  3. Bazzi, A., Fiorini, S., Pokutta, S., Svensson, O.: No small linear program approximates vertex cover within a factor \(2-\epsilon \). In: Proceedings of FOCS, pp. 1123–1142 (2015)

  4. Braun, G., Pokutta, S.: The matching polytope does not admit fully-polynomial size relaxation schemes. In: Proceedings of SODA, pp. 837–846 (2015). https://doi.org/10.1137/1.9781611973730.57

  5. Braun, G., Pokutta, S.: Common information and unique disjointness. Algorithmica 76(3), 597–629 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  6. Braun, G., Fiorini, S., Pokutta, S., Steurer, D.: Approximation limits of linear programs (beyond hierarchies). In: Proceedings of FOCS, pp. 480–489 (2012). ISBN 978-1-4673-4383-1. https://doi.org/10.1109/FOCS.2012.10

  7. Braun, G., Fiorini, S., Pokutta, S.: Average case polyhedral complexity of the maximum stable set problem. In: Proceedings of RANDOM (2014). http://www.dagstuhl.de/dagpub/978-3-939897-74-3. Accessed 12 Jan 2018

  8. Braun, G., Fiorini, S., Pokutta, S., Steurer, D.: Approximation limits of linear programs (beyond hierarchies). Math. Oper. Res. (2014). https://doi.org/10.1287/moor.2014.0694

    Article  MATH  Google Scholar 

  9. Braun, G., Jain, R., Lee, T., Pokutta, S.: Information-theoretic approximations of the nonnegative rank. Comput. Complex. 1–51 (2014). http://eccc.hpi-web.de/report/2013/158

  10. Braun, G., Pokutta, S., Zink, D.: Inapproximability of combinatorial problems via small LPs and SDPs. In: Proceeedings of STOC (2015)

  11. Braun, G., Brown-Cohen, J., Huq, A., Pokutta, S., Raghavendra, P., Roy, A., Weitz, B., Zink, D.: The matching problem has no small symmetric SDP. In: Proceedings of SODA, pp. 1067–1078 (2016)

  12. Braun, G., Fiorini, S., Pokutta, S.: Average case polyhedral complexity of the maximum stable set problem. Math. Program. 160(1), 407–431 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  13. Braun, G., Pokutta, S., Roy, A.: Strong reductions for extended formulations. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 350–361. Springer (2016)

  14. Braverman, M., Moitra, A.: An information complexity approach to extended formulations. In: Proceedings of STOC, pp. 161–170 (2013)

  15. Briët, J., Dadush, D., Pokutta, S.: On the existence of 0/1 polytopes with high semidefinite extension complexity. Math. Program. 153(1), 179–199 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  16. Chan, S., Lee, J., Raghavendra, P., Steurer, D.: Approximate constraint satisfaction requires large LP relaxations. In: Proceedings of FOCS, pp. 350–359 (2013). https://doi.org/10.1109/FOCS.2013.45

  17. Chan, S.O.: Approximation resistance from pairwise independent subgroups. In: Proceedings of STOC, pp. 447–456. ACM (2013). ISBN 978-1-4503-2029-0. https://doi.org/10.1145/2488608.2488665

  18. Charikar, M., Makarychev, K., Makarychev, Y.: Integrality gaps for Sherali–Adams relaxations. In: Proceedings of STOC, pp. 283–292 (2009)

  19. Chawla, S., Krauthgamer, R., Kumar, R., Rabani, Y., Sivakumar, D.: On the hardness of approximating multicut and sparsest-cut. Comput. Complex. 15(2), 94–114 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  20. Chlebík, M., Chlebíková, J.: On approximation hardness of the minimum 2SAT-DELETION problem. In: Mathematical Foundations of Computer Science 2004, pp. 263–273. Springer (2004)

  21. Engebretsen, L., Karpinski, M.: Approximation hardness of TSP with bounded metrics. In: Automata, Languages and Programming, volume 2076 of Lecture Notes in Computer Science, pp. 201–212. Springer, Berlin (2001). ISBN 978-3-540-42287-7 (print) and 978-3-540-48224-6 (online). https://doi.org/10.1007/3-540-48224-5_17. http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/2000/85220-CS.pdf. Accessed 12 Jan 2018

  22. Feige, U., Goemans, M.: Approximating the value of two power proof systems, with applications to Max 2SAT and Max DICUT. In: Theory of Computing and Systems, 1995. Proceedings, Third Israel Symposium on the, pp. 182–189. IEEE (1995)

  23. Feige, U., Goldwasser, S., Lovász, L., Safra, S., Szegedy, M.: Approximating clique is almost NP-complete. In: Proceedings of FOCS, pp. 2–12. IEEE Comput. Soc. Press (1991). ISBN 0-8186-2445-0. https://doi.org/10.1109/SFCS.1991.185341

  24. Feige, U., Karpinski, M., Langberg, M.: Improved approximation of Max-Cut on graphs of bounded degree. J. Algorithms 43(2), 201–219 (2002). ISSN 0196-6774. https://doi.org/10.1016/S0196-6774(02)00005-6. http://www.paradise.caltech.edu/~mikel/papers/deg_cut.ps

  25. Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., de Wolf, R.: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In: Proceedings of STOC (2012)

  26. Goemans, M.X., Williamson, D.P.: New 3/4-approximation algorithms for the maximum satisfiability problem. SIAM J. Discrete Math. 7(4), 656–666 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  27. Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach. 42, 1115–1145 (1995). https://doi.org/10.1145/227683.227684

    Article  MathSciNet  MATH  Google Scholar 

  28. Göös, M., Jain, R., Watson, T.: Extension complexity of independent set polytopes. In: Proceedings of FOCS, pp. 565–572. IEEE (2016)

  29. Gouveia, J., Parrilo, P.A., Thomas, R.R.: Lifts of convex sets and cone factorizations. Math. Oper. Res. 38(2), 248–264 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  30. Håstad, J.: Some optimal inapproximability results. J. ACM (JACM) 48(4), 798–859 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  31. Kaibel, V., Weltge, S.: A short proof that the extension complexity of the correlation polytope grows exponentially. Discrete Comput. Geom. 53(2), 397–401 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  32. Kann, V., Khanna, S., Lagergren, J., Panconesi, A.: On the hardness of approximating Max-\(k\)-CUT and its dual. Chic. J. Theor. Comput. Sci. 2, 1–18 (1997)

    MathSciNet  MATH  Google Scholar 

  33. Karloff, H.: How good is the Goemans–Williamson MAX CUT algorithm? SIAM J. Comput. 29(1), 336–350 (1999). https://doi.org/10.1137/S0097539797321481

    Article  MathSciNet  MATH  Google Scholar 

  34. Karpinski, M., Lampis, M., Schmied, R.: New inapproximability bounds for TSP. In: Algorithms and Computation, volume 8283 of Lecture Notes in Computer Science, pp. 568–578. Springer, Berlin (2013). ISBN 978-3-642-45029-7 (print) and 978-3-642-45030-3 (online). https://doi.org/10.1007/978-3-642-45030-3_53

  35. Khanna, S., Sudan, M., Trevisan, L., Williamson, D.P.: The approximability of constraint satisfaction problems. SIAM J. Comput. 30(6), 1863–1920 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  36. Khot, S., Kindler, G., Mossel, E., O’Donnell, R.: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput. 37(1), 319–357 (2007). https://doi.org/10.1137/S0097539705447372

    Article  MathSciNet  MATH  Google Scholar 

  37. Kothari, P., Meka, R., Raghavendra, P.: Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. arXiv preprint arXiv:1610.02704 (2016)

  38. Lee, J., Raghavendra, P., Steurer, D.: Lower bounds on the size of semidefinite programming relaxations. In: Proceedings of STOC (2015)

  39. Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425–440 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  40. Pashkovich, K.: Extended formulations for combinatorial polytopes. Ph.D. thesis, Magdeburg Universität (2012)

  41. Rothvoß, T.: Some 0/1 polytopes need exponential size extended formulations. Math. Program. 142(1–2), 255–268 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  42. Rothvoß, T.: The matching polytope has exponential extension complexity. In: Proceedings of STOC (2014)

  43. Schoenebeck, G.: Linear level Lasserre lower bounds for certain k-CSPs. In: Proceedings of FOCS, pp. 593–602 (2008). https://doi.org/10.1109/FOCS.2008.74

  44. Schrijver, A.: Theory of Linear Programming. Wiley-Interscience, New York (1986)

    MATH  Google Scholar 

  45. Singh, M.: Bellairs workshop on approximation algorithms. Open Probl. Sess. 1, 2 (2010)

    Google Scholar 

  46. Trevisan, L.: Parallel approximation algorithms by positive linear programming. Algorithmica 21(1), 72–88 (1998). ISSN 0178-4617 (print) and 1432-0541 (online). https://doi.org/10.1007/PL00009209

  47. Tulsiani, M.: CSP gaps and reductions in the Lasserre hierarchy. In: Proceedings of STOC, pp. 303–312. ACM (2009)

  48. Yannakakis, M.: Expressing combinatorial optimization problems by linear programs (extended abstract). In: Proceedings of STOC, pp. 223–228 (1988)

  49. Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43(3), 441–466 (1991). https://doi.org/10.1016/0022-0000(91)90024-Y

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

Research reported in this paper was partially supported by NSF Grant CMMI-1300144 and NSF CAREER Grant CMMI-1452463. The authors would like to thank James Lee for the helpful discussions regarding max-CSPs. We are indebted to Siu On Chan for some of the PCP inapproximability bounds as well as Santosh Vempala for the helpful discussions as well as the anonymous reviewers for significantly improving the presentation of the paper.

Author information

Authors and Affiliations

  1. ISyE, Georgia Institute of Technology, Atlanta, GA, USA

    Gábor Braun, Sebastian Pokutta & Daniel Zink

Authors
  1. Gábor Braun
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sebastian Pokutta
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Daniel Zink
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sebastian Pokutta.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Braun, G., Pokutta, S. & Zink, D. Affine reductions for LPs and SDPs. Math. Program. 173, 281–312 (2019). https://doi.org/10.1007/s10107-017-1221-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-017-1221-9

Mathematics Subject Classification

Search

Navigation