{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T04:42:06Z","timestamp":1725856926160},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319334608"},{"type":"electronic","value":"9783319334615"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-33461-5_29","type":"book-chapter","created":{"date-parts":[[2016,5,24]],"date-time":"2016-05-24T18:35:59Z","timestamp":1464114959000},"page":"350-361","source":"Crossref","is-referenced-by-count":2,"title":["Strong Reductions for Extended Formulations"],"prefix":"10.1007","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":"Aurko","family":"Roy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,5,25]]},"reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"Braun, G., Pokutta, S., Zink, D.: Inapproximability of combinatorial problems via small LPs and SDPs (2015)","DOI":"10.1145\/2746539.2746550"},{"issue":"3","key":"29_CR2","doi-asserted-by":"crossref","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)","journal-title":"J. Comput. Syst. Sci."},{"key":"29_CR3","doi-asserted-by":"crossref","unstructured":"Rothvo\u00df, T.: The matching polytope has exponential extension complexity. In: Proceedings of STOC, pp. 263\u2013272 (2014)","DOI":"10.1145\/2591796.2591834"},{"key":"29_CR4","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., de Wolf, R.: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. J. ACM (2015, to appear)"},{"key":"29_CR5","doi-asserted-by":"crossref","unstructured":"Lee, J.R., Raghavendra, P., Steurer, D.: Lower bounds on the size of semidefinite programming relaxations. arXiv preprint arXiv:1411.6317 (2014)","DOI":"10.1145\/2746539.2746599"},{"key":"29_CR6","doi-asserted-by":"crossref","unstructured":"Bazzi, A., Fiorini, S., Pokutta, S., Svensson, O.: No small linear program approximates Vertex Cover within a factor $$2-\\varepsilon $$ . arXiv preprint arXiv:1503.00753 (2015)","DOI":"10.1109\/FOCS.2015.73"},{"key":"29_CR7","unstructured":"Pashkovich, K.: Extended Formulations for Combinatorial Polytopes. Ph.D. thesis. Magdeburg Universit\u00e4t (2012)"},{"key":"29_CR8","doi-asserted-by":"crossref","unstructured":"Braun, G., Fiorini, S., Pokutta, S., Steurer, D.: Approximation limits of linear programs (beyond hierarchies). In: 53rd IEEE Symposium on Foundations of Computer Science (FOCS 2012), pp. 480\u2013489 (2012)","DOI":"10.1109\/FOCS.2012.10"},{"key":"29_CR9","doi-asserted-by":"crossref","unstructured":"Chan, S.O., Lee, J.R., Raghavendra, P., Steurer, D.: Approximate constraint satisfaction requires large LP relaxations. In: IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS 2013), pp. 350\u2013359. IEEE (2013)","DOI":"10.1109\/FOCS.2013.45"},{"key":"29_CR10","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G.: Linear level Lasserre lower bounds for certain k-CSPs. In: IEEE 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, pp. 593\u2013602. IEEE (2008)","DOI":"10.1109\/FOCS.2008.74"},{"key":"29_CR11","doi-asserted-by":"crossref","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Integrality gaps for Sherali-Adams relaxations. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pp. 283\u2013292. ACM (2009)","DOI":"10.1145\/1536414.1536455"},{"key":"29_CR12","doi-asserted-by":"crossref","unstructured":"Tulsiani, M.: CSP gaps and reductions in the Lasserre hierarchy. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pp. 303\u2013312. ACM (2009)","DOI":"10.1145\/1536414.1536457"},{"key":"29_CR13","unstructured":"Au, Y.H., Tun\u00e7el, L.: A comprehensive analysis of polyhedral lift-and-project methods. arXiv preprint (2013). arXiv:1312.5972"},{"issue":"1\u20133","key":"29_CR14","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/s10107-003-0407-5","volume":"98","author":"L Lipt\u00e1k","year":"2003","unstructured":"Lipt\u00e1k, L., Tun\u00e7el, L.: The stable set problem and the lift-and-project ranks of graphs. Math. Program. 98(1\u20133), 319\u2013353 (2003)","journal-title":"Math. Program."},{"issue":"1","key":"29_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.24.1.1","volume":"24","author":"T Stephen","year":"1999","unstructured":"Stephen, T., Tuncel, L.: On a representation of the matching polytope via semidefinite liftings. Math. Oper. Res. 24(1), 1\u20137 (1999)","journal-title":"Math. Oper. Res."},{"key":"29_CR16","unstructured":"Kolman, P., Kouteck\u00fd, M., Tiwary, H.R.: Extension complexity, MSO logic, and treewidth. CoRR abs\/1507.04907 (2015)"},{"key":"29_CR17","doi-asserted-by":"crossref","unstructured":"Gupta, A., Talwar, K., Witmer, D.: Sparsest cut on bounded treewidth graphs: algorithms and hardness results. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 281\u2013290. ACM (2013)","DOI":"10.1145\/2488608.2488644"},{"issue":"1","key":"29_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0894-0347-07-00573-5","volume":"21","author":"S Arora","year":"2008","unstructured":"Arora, S., Lee, J., Naor, A.: Euclidean distortion and the sparsest cut. J. Am. Math. Soc. 21(1), 1\u201321 (2008)","journal-title":"J. Am. Math. Soc."},{"key":"29_CR19","doi-asserted-by":"crossref","unstructured":"Cheeger, J., Kleiner, B., Naor, A.: A $$({\\rm log}\\, n)^{\\Omega (1)}$$ integrality gap for the sparsest cut SDP. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp. 555\u2013564. IEEE (2009)","DOI":"10.1109\/FOCS.2009.47"},{"issue":"2","key":"29_CR20","doi-asserted-by":"crossref","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."},{"issue":"6","key":"29_CR21","doi-asserted-by":"crossref","first-page":"2074","DOI":"10.1137\/S0097539797328847","volume":"29","author":"L Trevisan","year":"2000","unstructured":"Trevisan, L., Sorkin, G.B., Sudan, M., Williamson, D.P.: Gadgets, approximation, and linear programming. SIAM J. Comput. 29(6), 2074\u20132097 (2000)","journal-title":"SIAM J. Comput."},{"key":"29_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/978-3-642-20807-2_2","volume-title":"Integer Programming and Combinatoral Optimization","author":"YH Au","year":"2011","unstructured":"Au, Y.H., Tun\u00e7el, L.: Complexity analyses of Bienstock\u2013Zuckerberg and Lasserre relaxations on the matching and stable set polytopes. In: G\u00fcnl\u00fck, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol. 6655, pp. 14\u201326. Springer, Heidelberg (2011)"},{"key":"29_CR23","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Vijayaraghavan, A., Guruswami, V., Zhou, Y.: Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, pp. 388\u2013405 (2012)","DOI":"10.1137\/1.9781611973099.34"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-33461-5_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,8]],"date-time":"2019-09-08T15:47:07Z","timestamp":1567957627000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-33461-5_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319334608","9783319334615"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-33461-5_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}