{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:13:18Z","timestamp":1761621198254},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2014,12,17]],"date-time":"2014-12-17T00:00:00Z","timestamp":1418774400000},"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":["Math. Program."],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1007\/s10107-014-0855-0","type":"journal-article","created":{"date-parts":[[2014,12,16]],"date-time":"2014-12-16T11:10:55Z","timestamp":1418728255000},"page":"407-425","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Lower bounds on the sizes of integer programs without additional variables"],"prefix":"10.1007","volume":"154","author":[{"given":"Volker","family":"Kaibel","sequence":"first","affiliation":[]},{"given":"Stefan","family":"Weltge","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,12,17]]},"reference":[{"key":"855_CR1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"key":"855_CR2","doi-asserted-by":"crossref","unstructured":"Avis, D., Tiwary, H.R.: On the extension complexity of combinatorial polytopes. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M.Z., Peleg, D. (eds.) Automata, Languages, and Programming, Lecture Notes in Computer Science, vol. 7965, pp. 57\u201368. Springer, Berlin, Heidelberg (2013). doi: 10.1007\/978-3-642-39206-1_6","DOI":"10.1007\/978-3-642-39206-1_6"},{"key":"855_CR3","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: STOC, pp. 95\u2013106 (2012)","DOI":"10.1145\/2213977.2213988"},{"key":"855_CR4","unstructured":"Gavish, B., Graves, S.C.: The travelling salesman problem and related problems. Tech. rep, Operations Research Center, Massachusetts Institute of Technology (1978)"},{"key":"855_CR5","unstructured":"Goemans, M.: Smallest compact formulation for the permutahedron (to appear in a forthcoming issue of Mathematical Programming, Series B \u201cLifts of Convex Sets\u201d edited by V. Kaibel and R. Thomas) (2014). http:\/\/www-math.mit.edu\/~goemans\/publ.html"},{"issue":"2","key":"855_CR6","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0012-365X(75)90003-5","volume":"11","author":"R Jeroslow","year":"1975","unstructured":"Jeroslow, R.: On defining sets of vertices of the hypercube by linear inequalities. Discrete Math. 11(2), 119\u2013124 (1975)","journal-title":"Discrete Math."},{"key":"855_CR7","doi-asserted-by":"crossref","unstructured":"Kaibel, V., Weltge, S.: Lower bounds on the sizes of integer programs without additional variables. In: J. Lee, J. Vygen (eds.) Integer Programming and Combinatorial Optimization. Proceedings of IPCO XVII, Bonn, Lecture Notes in Computer Science, vol. 8494. Springer, Berlin (2014)","DOI":"10.1007\/978-3-319-07557-0_27"},{"issue":"3","key":"855_CR8","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1287\/ijoc.1060.0178","volume":"19","author":"J Lee","year":"2007","unstructured":"Lee, J., Margot, F.: On a binary-encoded ilp coloring formulation. INFORMS J. Comput. 19(3), 406\u2013415 (2007)","journal-title":"INFORMS J. Comput."},{"key":"855_CR9","doi-asserted-by":"crossref","unstructured":"Martin, R.K.: Using separation algorithms to generate mixed integer model reformulations. Oper. Res. Lett. 10(3), 119\u2013128 (1991). http:\/\/www.sciencedirect.com\/science\/article\/pii\/016763779190028N","DOI":"10.1016\/0167-6377(91)90028-N"},{"issue":"4","key":"855_CR10","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1145\/321043.321046","volume":"7","author":"CE Miller","year":"1960","unstructured":"Miller, C.E., Tucker, A.W., Zemlin, R.A.: Integer programming formulation of traveling salesman problems. J. ACM 7(4), 326\u2013329 (1960)","journal-title":"J. ACM"},{"key":"855_CR11","volume-title":"Geometrie der Zahlen","author":"H Minkowski","year":"1896","unstructured":"Minkowski, H.: Geometrie der Zahlen. Teubner Verlag, Leipzig (1896)"},{"key":"855_CR12","doi-asserted-by":"crossref","unstructured":"Pokutta, S., Vyve, M.V.: A note on the extension complexity of the knapsack polytope. Oper. Res. Lett. 41(4), 347\u2013350 (2013). doi: 10.1016\/j.orl.2013.03.010 . http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0167637713000394","DOI":"10.1016\/j.orl.2013.03.010"},{"key":"855_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1112\/jlms\/s1-27.1.1","volume":"27","author":"R Rado","year":"1952","unstructured":"Rado, R.: An inequality. J. Lond. Math. Soc. 27, 1\u20136 (1952)","journal-title":"J. Lond. Math. Soc."},{"key":"855_CR14","doi-asserted-by":"crossref","unstructured":"Rothvoss, T.: The matching polytope has exponential extension complexity. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC \u201914. ACM, New York, NY, pp. 263\u2013272 (2014). doi: 10.1145\/2591796.2591834","DOI":"10.1145\/2591796.2591834"},{"key":"855_CR15","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York, NY (1986)"},{"key":"855_CR16","volume-title":"Combinatorial Optimization\u2014Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization\u2014Polyhedra and Efficiency. Springer, Berlin (2003)"},{"issue":"3","key":"855_CR17","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."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0855-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-014-0855-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0855-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T06:00:06Z","timestamp":1559109606000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-014-0855-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,17]]},"references-count":17,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["855"],"URL":"https:\/\/doi.org\/10.1007\/s10107-014-0855-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,17]]}}}