{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T06:03:27Z","timestamp":1751349807340,"version":"3.37.3"},"reference-count":73,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,9,23]],"date-time":"2021-09-23T00:00:00Z","timestamp":1632355200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,9,23]],"date-time":"2021-09-23T00:00:00Z","timestamp":1632355200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1662757","1942065"],"award-info":[{"award-number":["1662757","1942065"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"crossref","award":["N00014-20-1-2242"],"award-info":[{"award-number":["N00014-20-1-2242"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,9]]},"DOI":"10.1007\/s10107-021-01706-2","type":"journal-article","created":{"date-parts":[[2021,9,23]],"date-time":"2021-09-23T12:14:08Z","timestamp":1632399248000},"page":"517-551","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Worst-case analysis of clique MIPs"],"prefix":"10.1007","volume":"195","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1373-4209","authenticated-orcid":false,"given":"Mohammad Javad","family":"Naderi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2999-9666","authenticated-orcid":false,"given":"Austin","family":"Buchanan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8258-7532","authenticated-orcid":false,"given":"Jose L.","family":"Walteros","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,9,23]]},"reference":[{"issue":"2","key":"1706_CR1","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1287\/ijoc.2018.0857","volume":"32","author":"T Achterberg","year":"2020","unstructured":"Achterberg, T., Bixby, R.E., Gu, Z., Rothberg, E., Weninger, D.: Presolve reductions in mixed integer programming. INFORMS J. Comput. 32(2), 473\u2013506 (2020)","journal-title":"INFORMS J. Comput."},{"issue":"3","key":"1706_CR2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process. Lett. 8(3), 121\u2013123 (1979)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"1706_CR3","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/S0377-2217(99)00015-6","volume":"121","author":"A Atamt\u00fcrk","year":"2000","unstructured":"Atamt\u00fcrk, A., Nemhauser, G.L., Savelsbergh, M.W.: Conflict graphs in solving integer programming problems. Eur. J. Oper. Res. 121(1), 40\u201355 (2000)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"1706_CR4","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1137\/0606047","volume":"6","author":"E Balas","year":"1985","unstructured":"Balas, E.: Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM J. Algebraic Discret. Methods 6(3), 466\u2013486 (1985)","journal-title":"SIAM J. Algebraic Discret. Methods"},{"issue":"6","key":"1706_CR5","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/0167-6377(88)90058-2","volume":"7","author":"E Balas","year":"1988","unstructured":"Balas, E.: On the convex hull of the union of certain polyhedra. Oper. Res. Lett. 7(6), 279\u2013283 (1988)","journal-title":"Oper. Res. Lett."},{"issue":"1\u20133","key":"1706_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(98)00136-X","volume":"89","author":"E Balas","year":"1998","unstructured":"Balas, E.: Disjunctive programming: properties of the convex hull of feasible points. Discret. Appl. Math. 89(1\u20133), 3\u201344 (1998)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"1706_CR7","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1287\/opre.1100.0851","volume":"59","author":"B Balasundaram","year":"2011","unstructured":"Balasundaram, B., Butenko, S., Hicks, I.V.: Clique relaxations in social network analysis: the maximum $$k$$-plex problem. Oper. Res. 59(1), 133\u2013142 (2011)","journal-title":"Oper. Res."},{"key":"1706_CR8","doi-asserted-by":"crossref","unstructured":"Basu, A., Conforti, M., Di\u00a0Summa, M., Jiang, H.: Complexity of cutting planes and branch-and-bound in mixed-integer optimization. arXiv:2003.05023 (2020)","DOI":"10.1007\/978-3-030-73879-2_27"},{"key":"1706_CR9","unstructured":"Batagelj, V., Zaversnik, M.: An $${O}(m)$$ algorithm for cores decomposition of networks. arXiv:cs\/0310049v1 (2003)"},{"issue":"1","key":"1706_CR10","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.disopt.2004.03.002","volume":"1","author":"D Bienstock","year":"2004","unstructured":"Bienstock, D., Ozbay, N.: Tree-width and the Sherali-Adams operator. Discret. Optim. 1(1), 13\u201321 (2004)","journal-title":"Discret. Optim."},{"issue":"1\u20133","key":"1706_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01588775","volume":"49","author":"C Blair","year":"1990","unstructured":"Blair, C.: Representation for multiple right-hand sides. Math. Program. 49(1\u20133), 1\u20135 (1990)","journal-title":"Math. Program."},{"issue":"1","key":"1706_CR12","doi-asserted-by":"publisher","first-page":"5","DOI":"10.7155\/jgaa.00117","volume":"10","author":"HL Bodlaender","year":"2006","unstructured":"Bodlaender, H.L., Koster, A.M., Wolle, T.: Contraction and treewidth lower bounds. J. Graph Algorithms Appl. 10(1), 5\u201349 (2006)","journal-title":"J. Graph Algorithms Appl."},{"key":"1706_CR13","doi-asserted-by":"crossref","unstructured":"Bomze, I.M., Budinich, M., Pardalos, P.M., Pelillo, M.: The maximum clique problem. In: Handbook of Combinatorial Optimization, pp. 1\u201374. Springer (1999)","DOI":"10.1007\/978-1-4757-3023-4_1"},{"issue":"3","key":"1706_CR14","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1287\/moor.2014.0694","volume":"40","author":"G Braun","year":"2015","unstructured":"Braun, G., Fiorini, S., Pokutta, S., Steurer, D.: Approximation limits of linear programs (beyond hierarchies). Math. Oper. Res. 40(3), 756\u2013772 (2015)","journal-title":"Math. Oper. Res."},{"key":"1706_CR15","doi-asserted-by":"crossref","unstructured":"Braverman, M., Moitra, A.: An information complexity approach to extended formulations. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 161\u2013170 (2013)","DOI":"10.1145\/2488608.2488629"},{"key":"1706_CR16","doi-asserted-by":"publisher","first-page":"105176","DOI":"10.1016\/j.cor.2020.105176","volume":"128","author":"SS Brito","year":"2021","unstructured":"Brito, S.S., Santos, H.G.: Preprocessing and cutting planes with conflict graphs. Comput. Oper. Res. 128, 105176 (2021)","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"1706_CR17","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1016\/j.orl.2016.03.008","volume":"44","author":"A Buchanan","year":"2016","unstructured":"Buchanan, A.: Extended formulations for vertex cover. Oper. Res. Lett. 44(3), 374\u2013378 (2016)","journal-title":"Oper. Res. Lett."},{"key":"1706_CR18","unstructured":"Buchanan, A., Butenko, S.: Tight extended formulations for independent set. Manuscript available on optimization online at http:\/\/www.optimization-online.org\/DB_FILE\/2014\/09\/4540.pdf (2015)"},{"issue":"5","key":"1706_CR19","doi-asserted-by":"publisher","first-page":"1611","DOI":"10.1007\/s11590-013-0698-2","volume":"8","author":"A Buchanan","year":"2014","unstructured":"Buchanan, A., Walteros, J.L., Butenko, S., Pardalos, P.M.: Solving maximum clique in sparse graphs: an $${O}(nm+ n2^{d\/4})$$ algorithm for $$d$$-degenerate graphs. Optim. Lett. 8(5), 1611\u20131617 (2014)","journal-title":"Optim. Lett."},{"key":"1706_CR20","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.tcs.2012.10.052","volume":"470","author":"J Chen","year":"2013","unstructured":"Chen, J., Kanj, I.A., Meng, J., Xia, G., Zhang, F.: Parameterized top-$$k$$ algorithms. Theor. Comput. Sci. 470, 105\u2013119 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"40\u201342","key":"1706_CR21","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40\u201342), 3736\u20133756 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"1706_CR22","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s10107-018-01358-9","volume":"180","author":"M Conforti","year":"2020","unstructured":"Conforti, M., Di Summa, M., Faenza, Y.: Balas formulation for the union of polytopes is optimal. Math. Program. 180(1), 311\u2013326 (2020)","journal-title":"Math. Program."},{"key":"1706_CR23","doi-asserted-by":"crossref","unstructured":"Coniglio, S., Gualandi, S.: Optimizing over the closure of rank inequalities with a small right-hand side for the maximum stable set problem via bilevel programming. INFORMS J. Comput. (2021) (to appear)","DOI":"10.1287\/ijoc.2021.1115"},{"key":"1706_CR24","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151\u2013158 (1971)","DOI":"10.1145\/800157.805047"},{"key":"1706_CR25","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2009)"},{"key":"1706_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141, Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"issue":"3","key":"1706_CR27","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1016\/0377-2217(94)90252-6","volume":"73","author":"FD Croce","year":"1994","unstructured":"Croce, F.D., Tadei, R.: A multi-KP modeling for the maximum-clique problem. Eur. J. Oper. Res. 73(3), 555\u2013561 (1994)","journal-title":"Eur. J. Oper. Res."},{"key":"1706_CR28","unstructured":"DIMACS. 10th DIMACS Implementation Challenge-Graph Partitioning and Graph Clustering. http:\/\/www.cc.gatech.edu\/dimacs10\/downloads.shtml (2020). Accessed 30 Dec 2020"},{"key":"1706_CR29","first-page":"3","volume":"18","author":"D Eppstein","year":"2013","unstructured":"Eppstein, D., L\u00f6ffler, M., Strash, D.: Listing all maximal cliques in large sparse real-world graphs. J. Exp. Algorithmics (JEA) 18, 3 (2013)","journal-title":"J. Exp. Algorithmics (JEA)"},{"key":"1706_CR30","doi-asserted-by":"crossref","unstructured":"Faenza, Y., Mu\u00f1oz, G., Pokutta, S.: New limits of treewidth-based tractability in optimization. In: Mathematical Programming (2020) (to appear)","DOI":"10.1007\/s10107-020-01563-5"},{"issue":"2","key":"1706_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2716307","volume":"62","author":"S Fiorini","year":"2015","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., De Wolf, R.: Exponential lower bounds for polytopes in combinatorial optimization. J. ACM (JACM) 62(2), 1\u201323 (2015)","journal-title":"J. ACM (JACM)"},{"key":"1706_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, P.: Exact Exponential Algorithms. Springer, Berlin (2010)"},{"key":"1706_CR33","unstructured":"Gleixner, A., Hendel, G., Gamrath, G., Achterberg, T., Bastubbe, M., Berthold, T., Christophel, P.M., Jarck, K., Koch, T., Linderoth, J., et\u00a0al.: MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library. Optimization Online preprint available at: http:\/\/www.optimization-online.org\/DB_HTML\/2019\/07\/7285.html (2019)"},{"key":"1706_CR34","unstructured":"Gomory, R.: An algorithm for the mixed integer problem. Technical Report P-1885, The RAND Corporation, Santa Monica (1960)"},{"issue":"1","key":"1706_CR35","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1137\/16M109884X","volume":"47","author":"M Goos","year":"2018","unstructured":"Goos, M., Jain, R., Watson, T.: Extension complexity of independent set polytopes. SIAM J. Comput. 47(1), 241\u2013269 (2018)","journal-title":"SIAM J. Comput."},{"key":"1706_CR36","unstructured":"Gurobi Optimization, Inc. Gurobi Optimizer Reference Manual (2020)"},{"issue":"1","key":"1706_CR37","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $${O}(n^{1-\\varepsilon })$$. Acta Math. 182(1), 105\u2013142 (1999)","journal-title":"Acta Math."},{"issue":"1","key":"1706_CR38","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/0377-2217(88)90013-6","volume":"36","author":"RG Jeroslow","year":"1988","unstructured":"Jeroslow, R.G.: A simplification for some disjunctive formulations. Eur. J. Oper. Res. 36(1), 116\u2013121 (1988)","journal-title":"Eur. J. Oper. Res."},{"key":"1706_CR39","doi-asserted-by":"crossref","unstructured":"Jeroslow, R.G., Lowe, J.K.: Modelling with integer variables. In: Mathematical Programming at Oberwolfach II, pp. 167\u2013184. Springer, Berlin (1984)","DOI":"10.1007\/BFb0121015"},{"key":"1706_CR40","doi-asserted-by":"crossref","unstructured":"Johnson, E.L., Padberg, M.W.: Degree-two inequalities, clique facets, and biperfect graphs. In: North-Holland Mathematics Studies, vol.\u00a066, pp. 169\u2013187. Elsevier, Amsterdam (1982)","DOI":"10.1016\/S0304-0208(08)72450-2"},{"key":"1706_CR41","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Springer, Berlin (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"4","key":"1706_CR42","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0108053","volume":"8","author":"JE Kelley Jr","year":"1960","unstructured":"Kelley, J.E., Jr.: The cutting-plane method for solving convex programs. J. Soc. Ind. Appl. Math. 8(4), 703\u2013712 (1960)","journal-title":"J. Soc. Ind. Appl. Math."},{"issue":"1","key":"1706_CR43","doi-asserted-by":"publisher","first-page":"A1","DOI":"10.37236\/1193","volume":"1","author":"DE Knuth","year":"1994","unstructured":"Knuth, D.E.: The sandwich theorem. Electron. J. Comb. 1(1), A1 (1994)","journal-title":"Electron. J. Comb."},{"issue":"2","key":"1706_CR44","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/s12532-011-0025-9","volume":"3","author":"T Koch","year":"2011","unstructured":"Koch, T., Achterberg, T., Andersen, E., Bastert, O., Berthold, T., Bixby, R.E., Danna, E., Gamrath, G., Gleixner, A.M., Heinz, S., et al.: MIPLIB 2010. Math. Program. Comput. 3(2), 103 (2011)","journal-title":"Math. Program. Comput."},{"issue":"4","key":"1706_CR45","first-page":"P4","volume":"22","author":"P Kolman","year":"2015","unstructured":"Kolman, P., Kouteck\u1ef3, M.: Extended formulation for CSP that is compact for instances of bounded treewidth. Electron. J. Comb. 22(4), P4-30 (2015)","journal-title":"Electron. J. Comb."},{"issue":"3","key":"1706_CR46","doi-asserted-by":"publisher","first-page":"497","DOI":"10.2307\/1910129","volume":"28","author":"AH Land","year":"1960","unstructured":"Land, A.H., Doig, A.G.: An automatic method of solving discrete programming problems. Econometrica 28(3), 497\u2013520 (1960)","journal-title":"Econometrica"},{"key":"1706_CR47","doi-asserted-by":"crossref","unstructured":"Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Emerging Applications of Algebraic Geometry, pp. 157\u2013270. Springer (2009)","DOI":"10.1007\/978-0-387-09686-5_7"},{"issue":"1","key":"1706_CR48","first-page":"1","volume":"8","author":"J Leskovec","year":"2016","unstructured":"Leskovec, J., Sosi\u010d, R.: SNAP: a general-purpose network analysis and graph-mining library. ACM Trans. Intell. Syst. Technol. (TIST) 8(1), 1\u201320 (2016)","journal-title":"ACM Trans. Intell. Syst. Technol. (TIST)"},{"key":"1706_CR49","doi-asserted-by":"publisher","first-page":"105024","DOI":"10.1016\/j.cor.2020.105024","volume":"123","author":"AN Letchford","year":"2020","unstructured":"Letchford, A.N., Rossi, F., Smriglio, S.: The stable set problem: clique and nodal inequalities revisited. Comput. Oper. Res. 123, 105024 (2020)","journal-title":"Comput. Oper. Res."},{"issue":"5","key":"1706_CR50","doi-asserted-by":"publisher","first-page":"1082","DOI":"10.4153\/CJM-1970-125-1","volume":"22","author":"DR Lick","year":"1970","unstructured":"Lick, D.R., White, A.T.: $$k$$-degenerate graphs. Can. J. Math. 22(5), 1082\u20131096 (1970)","journal-title":"Can. J. Math."},{"issue":"1","key":"1706_CR51","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"},{"key":"1706_CR52","unstructured":"Lowe, J.K.: Modelling with integer variables, Ph.D. thesis. Technical report, Georgia Institute of Technology (1984)"},{"issue":"2","key":"1706_CR53","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF02289146","volume":"14","author":"RD Luce","year":"1949","unstructured":"Luce, R.D., Perry, A.D.: A method of matrix analysis of group structure. Psychometrika 14(2), 95\u2013116 (1949)","journal-title":"Psychometrika"},{"key":"1706_CR54","unstructured":"Manoussakis, G.: The clique problem on inductive $$k$$-independent graphs. arXiv:1410.3302 (2014)"},{"issue":"7","key":"1706_CR55","doi-asserted-by":"publisher","first-page":"1348","DOI":"10.1016\/j.cor.2009.10.010","volume":"37","author":"P Martins","year":"2010","unstructured":"Martins, P.: Extended and discretized formulations for the maximum clique problem. Comput. Oper. Res. 37(7), 1348\u20131358 (2010)","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"1706_CR56","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1145\/2402.322385","volume":"30","author":"DW Matula","year":"1983","unstructured":"Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30(3), 417\u2013427 (1983)","journal-title":"J. ACM"},{"key":"1706_CR57","unstructured":"Miller, R.E., Muller, D.E.: A problem of maximum consistent subsets. Technical Report RC-240, IBM TJ Watson Research Center, New York (1960)"},{"issue":"3","key":"1706_CR58","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1287\/mnsc.30.3.290","volume":"30","author":"ID Moon","year":"1984","unstructured":"Moon, I.D., Chaudhry, S.S.: An analysis of network location problems with distance constraints. Manag. Sci. 30(3), 290\u2013307 (1984)","journal-title":"Manag. Sci."},{"issue":"1","key":"1706_CR59","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"JW Moon","year":"1965","unstructured":"Moon, J.W.: Moser, Leo: On cliques in graphs. Israel J. Math. 3(1), 23\u201328 (1965)","journal-title":"Israel J. Math."},{"issue":"3","key":"1706_CR60","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1016\/S0377-2217(96)00175-0","volume":"101","author":"AT Murray","year":"1997","unstructured":"Murray, A.T., Church, R.L.: Facets for node packing. Eur. J. Oper. Res. 101(3), 598\u2013608 (1997)","journal-title":"Eur. J. Oper. Res."},{"key":"1706_CR61","doi-asserted-by":"crossref","unstructured":"Nemhauser, G.L.: Trotter, L.E.: Properties of vertex packing and independence system polyhedra. Math. Program. 6(1), 48\u201361 (1974)","DOI":"10.1007\/BF01580222"},{"issue":"1","key":"1706_CR62","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"GL Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter, L.E.: Vertex packings: structural properties and algorithms. Math. Program. 8(1), 232\u2013248 (1975)","journal-title":"Math. Program."},{"issue":"1","key":"1706_CR63","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/BF01580121","volume":"5","author":"MW Padberg","year":"1973","unstructured":"Padberg, M.W.: On the facial structure of set packing polyhedra. Math. Program. 5(1), 199\u2013215 (1973)","journal-title":"Math. Program."},{"issue":"1","key":"1706_CR64","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.ejor.2012.10.021","volume":"226","author":"J Pattillo","year":"2013","unstructured":"Pattillo, J., Youssef, N., Butenko, S.: On clique relaxation models in network analysis. Eur. J. Oper. Res. 226(1), 9\u201318 (2013)","journal-title":"Eur. J. Oper. Res."},{"issue":"1\u20132","key":"1706_CR65","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1111\/j.1475-3995.2011.00805.x","volume":"19","author":"S Rebennack","year":"2012","unstructured":"Rebennack, S., Reinelt, G., Pardalos, P.M.: A tutorial on branch and cut algorithms for the maximum stable set problem. Int. Trans. Oper. Res. 19(1\u20132), 161\u2013199 (2012)","journal-title":"Int. Trans. Oper. Res."},{"issue":"5","key":"1706_CR66","doi-asserted-by":"publisher","first-page":"C589","DOI":"10.1137\/14100018X","volume":"37","author":"RA Rossi","year":"2015","unstructured":"Rossi, R.A., Gleich, D.F., Gebremedhin, A.H.: Parallel maximum clique algorithms with applications to network analysis. SIAM J. Sci. Comput. 37(5), C589\u2013C616 (2015)","journal-title":"SIAM J. Sci. Comput."},{"issue":"4","key":"1706_CR67","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1287\/ijoc.6.4.445","volume":"6","author":"MW Savelsbergh","year":"1994","unstructured":"Savelsbergh, M.W.: Preprocessing and probing techniques for mixed integer programming problems. ORSA J. Comput. 6(4), 445\u2013454 (1994)","journal-title":"ORSA J. Comput."},{"key":"1706_CR68","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)"},{"issue":"1","key":"1706_CR69","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1287\/ijoc.2014.0618","volume":"27","author":"A Verma","year":"2015","unstructured":"Verma, A., Buchanan, A., Butenko, S.: Solving the maximum clique and vertex coloring problems on very large sparse networks. INFORMS J. Comput. 27(1), 164\u2013177 (2015)","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"1706_CR70","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1137\/130915303","volume":"57","author":"JP Vielma","year":"2015","unstructured":"Vielma, J.P.: Mixed integer linear programming formulation techniques. SIAM Rev. 57(1), 3\u201357 (2015)","journal-title":"SIAM Rev."},{"issue":"6","key":"1706_CR71","doi-asserted-by":"publisher","first-page":"1866","DOI":"10.1287\/opre.2019.1970","volume":"68","author":"JL Walteros","year":"2020","unstructured":"Walteros, J.L., Buchanan, A.: Why is maximum clique often easy in practice? Oper. Res. 68(6), 1866\u20131895 (2020)","journal-title":"Oper. Res."},{"issue":"3","key":"1706_CR72","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)","journal-title":"J. Comput. Syst. Sci."},{"key":"1706_CR73","doi-asserted-by":"crossref","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC \u201906, pp. 681\u2013690 (2006)","DOI":"10.1145\/1132516.1132612"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01706-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01706-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01706-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T21:08:37Z","timestamp":1675717717000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01706-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,23]]},"references-count":73,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["1706"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01706-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2021,9,23]]},"assertion":[{"value":"7 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 September 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 September 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}