{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:04:52Z","timestamp":1787321092236,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We study the problem of optimizing an arbitrary weight function $w^Tz$ over the metric polytope of a graph $G=(V,E)$, a well-known relaxation of the cut polytope. We define the signed graph $(G, E^-)$, where $E^-$ consists of the edges of $G$ having negative weight. We characterize the sign patterns of the weight vector $w$ such that all optimal vertices of the metric polytope are integral, and we show that they correspond to signed graphs with no odd-$K_5$ minor. Our result has significant implications for unconstrained zero-one quadratic programming problems. We relate the strength of the cycle relaxation of the boolean quadric polytope to the sign pattern of the objective function. In this case, the sign patterns such that all optimal vertices of the cycle relaxation are integral correspond to signed graphs with no odd-$K_4$ minor.<\/jats:p>","DOI":"10.1137\/20m1318523","type":"journal-article","created":{"date-parts":[[2021,12,7]],"date-time":"2021-12-07T11:11:15Z","timestamp":1638875475000},"page":"2908-2921","source":"Crossref","is-referenced-by-count":2,"title":["Tight Cycle Relaxations for the Cut Polytope"],"prefix":"10.1137","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4717-816X","authenticated-orcid":true,"given":"Carla","family":"Michini","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,12,2]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01587084"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592023"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/0405014"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"G. Cornu\u00e9jols,\n                      Combinatorial Optimization: Packing and Covering\n                      , CBMS-NSF Regional Conf. Ser. in Appl. Math. 74, SIAM, Philadelphia, 2001,https:\/\/doi.org\/10.1137\/1.9780898717105.","DOI":"10.1137\/1.9780898717105"},{"key":"atypb5","unstructured":"Y. Crama,\n                      Linearization Techniques and Concave Extensions in Nonlinear \\textup0-1 Optimization\n                      , tech. rep., RUTCOR Research Report, 1988."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592027"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90056-N"},{"key":"atypb8","unstructured":"M. Deza and M. Laurent,\n                      Geometry of Cuts and Metrics\n                      , Algorithms Combin. 15, Springer, Berlin, Heidelberg, 2010."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/BF03006558"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/PL00011425"},{"key":"atypb11","unstructured":"M. Garey and D. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-Completeness\n                      , W. H. Freeman, San Francisco, CA, 1979."},{"key":"atypb12","unstructured":"A. Gerards,\n                      An Extension of K\u00f6nig's Theorem to Graphs with No Odd-$K_4$\n                      , research memorandum, Department of Economics, Tilburg Unversity, Tilburg, The Netherlands, 1986."},{"key":"atypb13","unstructured":"A. Gerards,\n                      Graphs and Polyhedra: Binary Spaces and Cutting Planes\n                      , CWI Tract 73, Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands, 1990."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2001.2051"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1287\/opre.13.3.388"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70343-1"},{"key":"atypb18","unstructured":"P. Hansen and B. Simeone,\n                      A Class of Quadratic Pseudoboolean Functions Whose Maximization is Reducible to a Network Flow Problem\n                      , tech. rep., CORR, 1979."},{"key":"atypb19","unstructured":"T. Huynh,\n                      The Linkage Problem for Group-labelled Graphs\n                      , Ph.D. thesis, University of Waterloo, Waterloo, ON, Canada, 2009."},{"key":"atypb20","first-page":"85","author":"Karp R. M.","year":"1972","journal-title":"MA"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"K. Kawarabayashi, B. Reed, and P. Wollan,\n                      The graph minor algorithm with parity conditions\n                      , in Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, 2011, pp. 27-36.","DOI":"10.1109\/FOCS.2011.52"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0328-8"},{"key":"atypb23","unstructured":"H. Minkowski,\n                      Geometrie der Zahlen\n                      , Teubner, Leipzig, Germany, 1896."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589101"},{"key":"atypb25","first-page":"569","author":"Poljak S.","year":"1991","journal-title":"Hungary"},{"key":"atypb26","unstructured":"A. Schrijver,\n                      Combinatorial Optimization: Polyhedra and Efficiency\n                      , Algorithms Combin. 24, Springer, Berlin, 2003."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(77)90031-4"},{"key":"atypb28","first-page":"3","author":"Weyl H.","year":"1951","journal-title":"NJ"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1318523","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:07:03Z","timestamp":1787317623000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1318523"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1318523"],"URL":"https:\/\/doi.org\/10.1137\/20m1318523","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}