{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T04:39:16Z","timestamp":1743136756269,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030179526"},{"type":"electronic","value":"9783030179533"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-17953-3_4","type":"book-chapter","created":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T23:17:39Z","timestamp":1556752659000},"page":"43-56","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Extended Formulations from Communication Protocols in Output-Efficient Time"],"prefix":"10.1007","author":[{"given":"Manuel","family":"Aprile","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuri","family":"Faenza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,13]]},"reference":[{"key":"4_CR1","unstructured":"Aprile, M.: On some problems related to 2-level polytopes. Ph.D. thesis, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne (2018)"},{"key":"4_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-319-68705-6_6","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M Aprile","year":"2017","unstructured":"Aprile, M., Faenza, Y., Fiorini, S., Huynh, T., Macchia, M.: Extension complexity of stable set polytopes of\u00a0bipartite graphs. In: Bodlaender, H.L., Woeginger, G.J. (eds.) WG 2017. LNCS, vol. 10520, pp. 75\u201387. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-68705-6_6"},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0167-5060(08)70342-X","volume":"5","author":"E Balas","year":"1979","unstructured":"Balas, E.: Disjunctive programming. Ann. Discrete Math. 5, 3\u201351 (1979)","journal-title":"Ann. Discrete Math."},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Bazzi, A., Fiorini, S., Huang, S., Svensson, O.: Small extended formulation for knapsack cover inequalities from monotone circuits. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2326\u20132341. SIAM (2017)","DOI":"10.1137\/1.9781611974782.153"},{"issue":"1","key":"4_CR5","first-page":"147","volume":"44","author":"A Bazzi","year":"2018","unstructured":"Bazzi, A., Fiorini, S., Pokutta, S., Svensson, O.: No small linear program approximates vertex cover within a factor $$2-\\epsilon $$. Math. Oper. Res. 44(1), 147\u2013172 (2018)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"4_CR6","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1145\/2811255","volume":"63","author":"SO Chan","year":"2016","unstructured":"Chan, S.O., Lee, J.R., Raghavendra, P., Steurer, D.: Approximate constraint satisfaction requires large LP relaxations. J. ACM (JACM) 63(4), 34 (2016)","journal-title":"J. ACM (JACM)"},{"key":"4_CR7","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.jctb.2015.04.007","volume":"115","author":"M Chudnovsky","year":"2015","unstructured":"Chudnovsky, M., Trotignon, N., Trunck, T., Vu\u0161kovi\u0107, K.: Coloring perfect graphs with no balanced skew-partitions. J. Comb. Theory Ser. B 115, 26\u201365 (2015)","journal-title":"J. Comb. Theory Ser. B"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/0095-8956(75)90041-6","volume":"18","author":"V Chv\u00e1tal","year":"1975","unstructured":"Chv\u00e1tal, V.: On certain polytopes associated with graphs. J. Comb. Theory Ser. B 18, 138\u2013154 (1975)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"4_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10288-010-0122-z","volume":"8","author":"M Conforti","year":"2010","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Extended formulations in combinatorial optimization. 4OR 8(1), 1\u201348 (2010)","journal-title":"4OR"},{"issue":"1","key":"4_CR10","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s10107-014-0755-3","volume":"153","author":"Y Faenza","year":"2015","unstructured":"Faenza, Y., Fiorini, S., Grappe, R., Tiwary, H.R.: Extended formulations, nonnegative factorizations, and randomized communication protocols. Math. Program. 153(1), 75\u201394 (2015)","journal-title":"Math. Program."},{"key":"4_CR11","unstructured":"Fiorini, S., Huynh, T., Weltge, S.: Strengthening convex relaxations of 0\/1-sets using Boolean formulas. arXiv preprint arXiv:1711.01358 (2017)"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"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 the Forty-Fourth Annual ACM Symposium on Theory of Computing, pp. 95\u2013106. ACM (2012)","DOI":"10.1145\/2213977.2213988"},{"issue":"3","key":"4_CR13","doi-asserted-by":"publisher","first-page":"1944","DOI":"10.1137\/140966332","volume":"25","author":"M Giandomenico","year":"2015","unstructured":"Giandomenico, M., Letchford, A.N., Rossi, F., Smriglio, S.: Ellipsoidal relaxations of the stable set problem: theory and algorithms. SIAM J. Optim. 25(3), 1944\u20131963 (2015)","journal-title":"SIAM J. Optim."},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M.: Lower bounds for clique vs. independent set. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 1066\u20131076. IEEE (2015)","DOI":"10.1109\/FOCS.2015.69"},{"issue":"1","key":"4_CR15","first-page":"241","volume":"47","author":"M G\u00f6\u00f6s","year":"2018","unstructured":"G\u00f6\u00f6s, M., Jain, R., Watson, T.: Extension complexity of independent set polytopes. SIAM J. Optim. 47(1), 241\u2013269 (2018)","journal-title":"SIAM J. Optim."},{"key":"4_CR16","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/S0304-0208(08)72943-8","volume":"88","author":"M Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Polynomial algorithms for perfect graphs. N.-Holl. Math. Stud. 88, 325\u2013356 (1984)","journal-title":"N.-Holl. Math. Stud."},{"issue":"4","key":"4_CR17","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)"},{"key":"4_CR18","first-page":"2","volume":"85","author":"V Kaibel","year":"2011","unstructured":"Kaibel, V.: Extended formulations in combinatorial optimization. OPTIMA 85, 2\u20137 (2011)","journal-title":"OPTIMA"},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-642-38189-8_4","volume-title":"Facets of Combinatorial Optimization","author":"V Kaibel","year":"2013","unstructured":"Kaibel, V., Pashkovich, K.: Constructing extended formulations from reflection relations. In: J\u00fcnger, M., Reinelt, G. (eds.) Facets of Combinatorial Optimization, pp. 77\u2013100. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38189-8_4"},{"key":"4_CR20","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574948","volume-title":"Communication Complexity","author":"E Kushilevitz","year":"1996","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1996)"},{"key":"4_CR21","unstructured":"Lagoutte, A.: Personal communication, Cargese, Corsica, 18 October 2018"},{"issue":"1","key":"4_CR22","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.disopt.2003.12.001","volume":"1","author":"J Lee","year":"2004","unstructured":"Lee, J., Leung, J., Margot, F.: Min-up\/min-down polytopes. Discrete Optim. 1(1), 77\u201385 (2004)","journal-title":"Discrete Optim."},{"issue":"1","key":"4_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25(1), 1\u20137 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1\u20133","key":"4_CR24","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/0012-365X(92)00057-X","volume":"124","author":"L Lov\u00e1sz","year":"1994","unstructured":"Lov\u00e1sz, L.: Stable sets and polynomials. Discrete Math. 124(1\u20133), 137\u2013153 (1994)","journal-title":"Discrete Math."},{"issue":"3","key":"4_CR25","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0167-6377(91)90028-N","volume":"10","author":"RK Martin","year":"1991","unstructured":"Martin, R.K.: Using separation algorithms to generate mixed integer model reformulations. Oper. Res. Lett. 10(3), 119\u2013128 (1991)","journal-title":"Oper. Res. Lett."},{"key":"4_CR26","unstructured":"Pashkovich, K.: Extended formulations for combinatorial polytopes. Ph.D. thesis, Otto-von-Guericke-Universit\u00e4t Magdeburg (2012)"},{"issue":"6","key":"4_CR27","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/3127497","volume":"64","author":"T Rothvo\u00df","year":"2017","unstructured":"Rothvo\u00df, T.: The matching polytope has exponential extension complexity. J. ACM (JACM) 64(6), 41 (2017)","journal-title":"J. ACM (JACM)"},{"key":"4_CR28","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2002","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer, Heidelberg (2002)"},{"key":"4_CR29","unstructured":"Weltge, S.: Sizes of linear descriptions in combinatorial optimization. Ph.D. thesis, Otto-von-Guericke-Universit\u00e4t Magdeburg, Fakult\u00e4t f\u00fcr Mathematik (2015)"},{"key":"4_CR30","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, 441\u2013466 (1991)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-17953-3_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T12:41:22Z","timestamp":1709815282000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-17953-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030179526","9783030179533"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-17953-3_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"13 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ann Arbor, MI","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 May 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 May 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/umich.edu\/~ipco2019conf\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"113","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"29% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2.5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}