{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T02:24:14Z","timestamp":1773800654994,"version":"3.50.1"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2018,1,16]],"date-time":"2018-01-16T00:00:00Z","timestamp":1516060800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,1,16]],"date-time":"2018-01-16T00:00:00Z","timestamp":1516060800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000147","name":"Division of Civil, Mechanical and Manufacturing Innovation","doi-asserted-by":"publisher","award":["CMMI-1300144"],"award-info":[{"award-number":["CMMI-1300144"]}],"id":[{"id":"10.13039\/100000147","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000147","name":"Division of Civil, Mechanical and Manufacturing Innovation","doi-asserted-by":"publisher","award":["CMMI-1452463"],"award-info":[{"award-number":["CMMI-1452463"]}],"id":[{"id":"10.13039\/100000147","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2019,1]]},"DOI":"10.1007\/s10107-017-1221-9","type":"journal-article","created":{"date-parts":[[2018,1,16]],"date-time":"2018-01-16T04:52:18Z","timestamp":1516078338000},"page":"281-312","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Affine reductions for LPs and SDPs"],"prefix":"10.1007","volume":"173","author":[{"given":"G\u00e1bor","family":"Braun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Pokutta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Zink","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,1,16]]},"reference":[{"key":"1221_CR1","doi-asserted-by":"crossref","unstructured":"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\u2013581. ACM (2005)","DOI":"10.1145\/1060590.1060675"},{"key":"1221_CR2","doi-asserted-by":"crossref","unstructured":"Austrin, P., Khot, S., Safra, M.: Inapproximability of vertex cover and independent set in bounded degree graphs. In: Computational Complexity, CCC, pp. 74\u201380. IEEE (2009)","DOI":"10.1109\/CCC.2009.38"},{"key":"1221_CR3","doi-asserted-by":"crossref","unstructured":"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\u20131142 (2015)","DOI":"10.1109\/FOCS.2015.73"},{"key":"1221_CR4","doi-asserted-by":"crossref","unstructured":"Braun, G., Pokutta, S.: The matching polytope does not admit fully-polynomial size relaxation schemes. In: Proceedings of SODA, pp. 837\u2013846 (2015). https:\/\/doi.org\/10.1137\/1.9781611973730.57","DOI":"10.1137\/1.9781611973730.57"},{"issue":"3","key":"1221_CR5","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/s00453-016-0132-0","volume":"76","author":"G Braun","year":"2016","unstructured":"Braun, G., Pokutta, S.: Common information and unique disjointness. Algorithmica 76(3), 597\u2013629 (2016)","journal-title":"Algorithmica"},{"key":"1221_CR6","doi-asserted-by":"crossref","unstructured":"Braun, G., Fiorini, S., Pokutta, S., Steurer, D.: Approximation limits of linear programs (beyond hierarchies). In: Proceedings of FOCS, pp. 480\u2013489 (2012). ISBN 978-1-4673-4383-1. https:\/\/doi.org\/10.1109\/FOCS.2012.10","DOI":"10.1109\/FOCS.2012.10"},{"key":"1221_CR7","unstructured":"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"},{"key":"1221_CR8","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2014.0694","author":"G Braun","year":"2014","unstructured":"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","journal-title":"Math. Oper. Res."},{"key":"1221_CR9","unstructured":"Braun, G., Jain, R., Lee, T., Pokutta, S.: Information-theoretic approximations of the nonnegative rank. Comput. Complex. 1\u201351 (2014). http:\/\/eccc.hpi-web.de\/report\/2013\/158"},{"key":"1221_CR10","doi-asserted-by":"crossref","unstructured":"Braun, G., Pokutta, S., Zink, D.: Inapproximability of combinatorial problems via small LPs and SDPs. In: Proceeedings of STOC (2015)","DOI":"10.1145\/2746539.2746550"},{"key":"1221_CR11","doi-asserted-by":"crossref","unstructured":"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\u20131078 (2016)","DOI":"10.1137\/1.9781611974331.ch75"},{"issue":"1","key":"1221_CR12","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/s10107-016-0989-3","volume":"160","author":"G Braun","year":"2016","unstructured":"Braun, G., Fiorini, S., Pokutta, S.: Average case polyhedral complexity of the maximum stable set problem. Math. Program. 160(1), 407\u2013431 (2016)","journal-title":"Math. Program."},{"key":"1221_CR13","doi-asserted-by":"crossref","unstructured":"Braun, G., Pokutta, S., Roy, A.: Strong reductions for extended formulations. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 350\u2013361. Springer (2016)","DOI":"10.1007\/978-3-319-33461-5_29"},{"key":"1221_CR14","doi-asserted-by":"crossref","unstructured":"Braverman, M., Moitra, A.: An information complexity approach to extended formulations. In: Proceedings of STOC, pp. 161\u2013170 (2013)","DOI":"10.1145\/2488608.2488629"},{"issue":"1","key":"1221_CR15","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s10107-014-0785-x","volume":"153","author":"J Bri\u00ebt","year":"2015","unstructured":"Bri\u00ebt, J., Dadush, D., Pokutta, S.: On the existence of 0\/1 polytopes with high semidefinite extension complexity. Math. Program. 153(1), 179\u2013199 (2015)","journal-title":"Math. Program."},{"key":"1221_CR16","doi-asserted-by":"crossref","unstructured":"Chan, S., Lee, J., Raghavendra, P., Steurer, D.: Approximate constraint satisfaction requires large LP relaxations. In: Proceedings of FOCS, pp. 350\u2013359 (2013). https:\/\/doi.org\/10.1109\/FOCS.2013.45","DOI":"10.1109\/FOCS.2013.45"},{"key":"1221_CR17","doi-asserted-by":"crossref","unstructured":"Chan, S.O.: Approximation resistance from pairwise independent subgroups. In: Proceedings of STOC, pp. 447\u2013456. ACM (2013). ISBN 978-1-4503-2029-0. https:\/\/doi.org\/10.1145\/2488608.2488665","DOI":"10.1145\/2488608.2488665"},{"key":"1221_CR18","doi-asserted-by":"crossref","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Integrality gaps for Sherali\u2013Adams relaxations. In: Proceedings of STOC, pp. 283\u2013292 (2009)","DOI":"10.1145\/1536414.1536455"},{"issue":"2","key":"1221_CR19","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/s00037-006-0210-9","volume":"15","author":"S Chawla","year":"2006","unstructured":"Chawla, S., Krauthgamer, R., Kumar, R., Rabani, Y., Sivakumar, D.: On the hardness of approximating multicut and sparsest-cut. Comput. Complex. 15(2), 94\u2013114 (2006)","journal-title":"Comput. Complex."},{"key":"1221_CR20","doi-asserted-by":"crossref","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: On approximation hardness of the minimum 2SAT-DELETION problem. In: Mathematical Foundations of Computer Science 2004, pp. 263\u2013273. Springer (2004)","DOI":"10.1007\/978-3-540-28629-5_18"},{"key":"1221_CR21","unstructured":"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\u2013212. 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"},{"key":"1221_CR22","doi-asserted-by":"crossref","unstructured":"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\u2013189. IEEE (1995)","DOI":"10.1109\/ISTCS.1995.377033"},{"key":"1221_CR23","doi-asserted-by":"crossref","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Approximating clique is almost NP-complete. In: Proceedings of FOCS, pp. 2\u201312. IEEE Comput. Soc. Press (1991). ISBN 0-8186-2445-0. https:\/\/doi.org\/10.1109\/SFCS.1991.185341","DOI":"10.1109\/SFCS.1991.185341"},{"key":"1221_CR24","unstructured":"Feige, U., Karpinski, M., Langberg, M.: Improved approximation of Max-Cut on graphs of bounded degree. J. Algorithms 43(2), 201\u2013219 (2002). ISSN 0196-6774. https:\/\/doi.org\/10.1016\/S0196-6774(02)00005-6 . http:\/\/www.paradise.caltech.edu\/~mikel\/papers\/deg_cut.ps"},{"key":"1221_CR25","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., de\u00a0Wolf, R.: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In: Proceedings of STOC (2012)","DOI":"10.1145\/2213977.2213988"},{"issue":"4","key":"1221_CR26","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"MX Goemans","year":"1994","unstructured":"Goemans, M.X., Williamson, D.P.: New 3\/4-approximation algorithms for the maximum satisfiability problem. SIAM J. Discrete Math. 7(4), 656\u2013666 (1994)","journal-title":"SIAM J. Discrete Math."},{"key":"1221_CR27","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach. 42, 1115\u20131145 (1995). https:\/\/doi.org\/10.1145\/227683.227684","journal-title":"J. Assoc. Comput. Mach."},{"key":"1221_CR28","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Jain, R., Watson, T.: Extension complexity of independent set polytopes. In: Proceedings of FOCS, pp. 565\u2013572. IEEE (2016)","DOI":"10.1109\/FOCS.2016.67"},{"issue":"2","key":"1221_CR29","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1287\/moor.1120.0575","volume":"38","author":"J Gouveia","year":"2013","unstructured":"Gouveia, J., Parrilo, P.A., Thomas, R.R.: Lifts of convex sets and cone factorizations. Math. Oper. Res. 38(2), 248\u2013264 (2013)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"1221_CR30","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM (JACM) 48(4), 798\u2013859 (2001)","journal-title":"J. ACM (JACM)"},{"issue":"2","key":"1221_CR31","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/s00454-014-9655-9","volume":"53","author":"V Kaibel","year":"2015","unstructured":"Kaibel, V., Weltge, S.: A short proof that the extension complexity of the correlation polytope grows exponentially. Discrete Comput. Geom. 53(2), 397\u2013401 (2015)","journal-title":"Discrete Comput. Geom."},{"key":"1221_CR32","first-page":"1","volume":"2","author":"V Kann","year":"1997","unstructured":"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\u201318 (1997)","journal-title":"Chic. J. Theor. Comput. Sci."},{"issue":"1","key":"1221_CR33","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1137\/S0097539797321481","volume":"29","author":"H Karloff","year":"1999","unstructured":"Karloff, H.: How good is the Goemans\u2013Williamson MAX CUT algorithm? SIAM J. Comput. 29(1), 336\u2013350 (1999). https:\/\/doi.org\/10.1137\/S0097539797321481","journal-title":"SIAM J. Comput."},{"key":"1221_CR34","doi-asserted-by":"crossref","unstructured":"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\u2013578. 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","DOI":"10.1007\/978-3-642-45030-3_53"},{"issue":"6","key":"1221_CR35","doi-asserted-by":"publisher","first-page":"1863","DOI":"10.1137\/S0097539799349948","volume":"30","author":"S Khanna","year":"2001","unstructured":"Khanna, S., Sudan, M., Trevisan, L., Williamson, D.P.: The approximability of constraint satisfaction problems. SIAM J. Comput. 30(6), 1863\u20131920 (2001)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1221_CR36","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1137\/S0097539705447372","volume":"37","author":"S Khot","year":"2007","unstructured":"Khot, S., Kindler, G., Mossel, E., O\u2019Donnell, R.: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput. 37(1), 319\u2013357 (2007). https:\/\/doi.org\/10.1137\/S0097539705447372","journal-title":"SIAM J. Comput."},{"key":"1221_CR37","doi-asserted-by":"crossref","unstructured":"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)","DOI":"10.1145\/3055399.3055438"},{"key":"1221_CR38","doi-asserted-by":"crossref","unstructured":"Lee, J., Raghavendra, P., Steurer, D.: Lower bounds on the size of semidefinite programming relaxations. In: Proceedings of STOC (2015)","DOI":"10.1145\/2746539.2746599"},{"issue":"3","key":"1221_CR39","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"1221_CR40","unstructured":"Pashkovich, K.: Extended formulations for combinatorial polytopes. Ph.D. thesis, Magdeburg Universit\u00e4t (2012)"},{"issue":"1\u20132","key":"1221_CR41","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/s10107-012-0574-3","volume":"142","author":"T Rothvo\u00df","year":"2013","unstructured":"Rothvo\u00df, T.: Some 0\/1 polytopes need exponential size extended formulations. Math. Program. 142(1\u20132), 255\u2013268 (2013)","journal-title":"Math. Program."},{"key":"1221_CR42","doi-asserted-by":"crossref","unstructured":"Rothvo\u00df, T.: The matching polytope has exponential extension complexity. In: Proceedings of STOC (2014)","DOI":"10.1145\/2591796.2591834"},{"key":"1221_CR43","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G.: Linear level Lasserre lower bounds for certain k-CSPs. In: Proceedings of FOCS, pp. 593\u2013602 (2008). https:\/\/doi.org\/10.1109\/FOCS.2008.74","DOI":"10.1109\/FOCS.2008.74"},{"key":"1221_CR44","volume-title":"Theory of Linear Programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear Programming. Wiley-Interscience, New York (1986)"},{"key":"1221_CR45","first-page":"2","volume":"1","author":"M Singh","year":"2010","unstructured":"Singh, M.: Bellairs workshop on approximation algorithms. Open Probl. Sess. 1, 2 (2010)","journal-title":"Open Probl. Sess."},{"key":"1221_CR46","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: Parallel approximation algorithms by positive linear programming. Algorithmica 21(1), 72\u201388 (1998). ISSN 0178-4617 (print) and 1432-0541 (online). https:\/\/doi.org\/10.1007\/PL00009209","DOI":"10.1007\/PL00009209"},{"key":"1221_CR47","doi-asserted-by":"crossref","unstructured":"Tulsiani, M.: CSP gaps and reductions in the Lasserre hierarchy. In: Proceedings of STOC, pp. 303\u2013312. ACM (2009)","DOI":"10.1145\/1536414.1536457"},{"key":"1221_CR48","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Expressing combinatorial optimization problems by linear programs (extended abstract). In: Proceedings of STOC, pp. 223\u2013228 (1988)","DOI":"10.1145\/62212.62232"},{"issue":"3","key":"1221_CR49","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/0022-0000(91)90024-Y","volume":"43","author":"M Yannakakis","year":"1991","unstructured":"Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43(3), 441\u2013466 (1991). https:\/\/doi.org\/10.1016\/0022-0000(91)90024-Y","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-017-1221-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1221-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1221-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,29]],"date-time":"2025-06-29T21:32:46Z","timestamp":1751232766000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-017-1221-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,16]]},"references-count":49,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["1221"],"URL":"https:\/\/doi.org\/10.1007\/s10107-017-1221-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1,16]]},"assertion":[{"value":"29 December 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 December 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 January 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}