{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:26:14Z","timestamp":1759667174883,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"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_16","type":"book-chapter","created":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T23:25:20Z","timestamp":1556753120000},"page":"205-218","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Bundle Approach for SDPs with Exact Subgraph Constraints"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1643-6066","authenticated-orcid":false,"given":"Elisabeth","family":"Gaar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1578-9414","authenticated-orcid":false,"given":"Franz","family":"Rendl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,13]]},"reference":[{"issue":"1","key":"16_CR1","first-page":"40","volume":"53","author":"E Adams","year":"2015","unstructured":"Adams, E., Anjos, M.F., Rendl, F., Wiegele, A.: A hierarchy of subgraph projection-based semidefinite relaxations for some NP-hard graph optimization problems. INFOR Inf. Syst. Oper. Res. 53(1), 40\u201347 (2015)","journal-title":"INFOR Inf. Syst. Oper. Res."},{"key":"16_CR2","unstructured":"Biq Mac Library. http:\/\/biqmac.aau.at\/. Accessed 18 Nov 2018"},{"issue":"2","key":"16_CR3","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0167-6377(90)90044-6","volume":"9","author":"E Boros","year":"1990","unstructured":"Boros, E., Crama, Y., Hammer, P.L.: Upper-bounds for quadratic $$0$$-$$1$$ maximization. Oper. Res. Lett. 9(2), 73\u201379 (1990)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"16_CR4","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/BF01585184","volume":"62","author":"C Delorme","year":"1993","unstructured":"Delorme, C., Poljak, S.: Laplacian eigenvalues and the maximum cut problem. Math. Program. Ser. A 62(3), 557\u2013574 (1993)","journal-title":"Math. Program. Ser. A"},{"key":"16_CR5","unstructured":"DIMACS Implementation Challenges (1992). http:\/\/dimacs.rutgers.edu\/Challenges\/. Accessed 18 Nov 2018"},{"issue":"1","key":"16_CR6","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s10107-013-0642-3","volume":"145","author":"A Frangioni","year":"2014","unstructured":"Frangioni, A., Gorgone, E.: Bundle methods for sum-functions with \u201ceasy\u201d components: applications to multicommodity network design. Math. Program. 145(1), 133\u2013161 (2014)","journal-title":"Math. Program."},{"key":"16_CR7","unstructured":"Gaar, E.: Efficient Implementation of SDP Relaxations for the Stable Set Problem. Ph.D. thesis, Alpen-Adria-Universit\u00e4t Klagenfurt (2018)"},{"issue":"6","key":"16_CR8","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(6), 1115\u20131145 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"key":"16_CR9","series-title":"Study and Research Texts","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics. Study and Research Texts, vol. 2. Springer, Berlin (1988)"},{"issue":"1","key":"16_CR10","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/S0895480100376794","volume":"18","author":"V Guruswami","year":"2004","unstructured":"Guruswami, V., Khanna, S.: On the hardness of 4-coloring a 3-colorable graph. SIAM J. Discrete Math. 18(1), 30\u201340 (2004)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"16_CR11","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 $$n^{1-\\epsilon }$$. Acta Math. 182(1), 105\u2013142 (1999)","journal-title":"Acta Math."},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Khot, S.: Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring. In: 42nd IEEE Symposium on Foundations of Computer Science, Las Vegas, NV, pp. 600\u2013609. IEEE Computer Society, Los Alamitos (2001)","DOI":"10.1109\/SFCS.2001.959936"},{"key":"16_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/3-540-45535-3_23","volume-title":"Integer Programming and Combinatorial Optimization","author":"JB Lasserre","year":"2001","unstructured":"Lasserre, J.B.: An Explicit exact SDP relaxation for nonlinear 0-1 programs. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol. 2081, pp. 293\u2013303. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-45535-3_23"},{"issue":"1","key":"16_CR14","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":"2","key":"16_CR15","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and $$0$$-$$1$$ optimization. SIAM J. Optim. 1(2), 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"key":"16_CR16","unstructured":"MOSEK ApS: The MOSEK optimization toolbox for MATLAB manual. Version 8.0. (2017). http:\/\/docs.mosek.com\/8.0\/toolbox\/index.html"},{"key":"16_CR17","unstructured":"Nguyen, T.H., Bui, T.: Graph coloring benchmark instances. https:\/\/turing.cs.hbg.psu.edu\/txn131\/graphcoloring.html. Accessed 18 Nov 2018"},{"issue":"2","key":"16_CR18","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/s10107-008-0235-8","volume":"121","author":"F Rendl","year":"2010","unstructured":"Rendl, F., Rinaldi, G., Wiegele, A.: Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Program. Ser. A 121(2), 307\u2013335 (2010)","journal-title":"Math. Program. Ser. A"},{"key":"16_CR19","series-title":"Princeton Mathematical Series","doi-asserted-by":"publisher","DOI":"10.1515\/9781400873173","volume-title":"Convex Analysis","author":"RT Rockafellar","year":"1970","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton Mathematical Series, vol. 28. Princeton University Press, Princeton (1970)"},{"issue":"3","key":"16_CR20","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"HD Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3), 411\u2013430 (1990)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"16_CR21","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10107-002-0347-5","volume":"95","author":"RH T\u00fct\u00fcnc\u00fc","year":"2003","unstructured":"T\u00fct\u00fcnc\u00fc, R.H., Toh, K.C., Todd, M.J.: Solving semidefinite-quadratic-linear programs using SDPT3. Math. Program. Ser. B 95(2), 189\u2013217 (2003)","journal-title":"Math. Program. Ser. B"}],"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_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T12:42:30Z","timestamp":1709815350000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-17953-3_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030179526","9783030179533"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-17953-3_16","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)"}}]}}