{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T11:56:35Z","timestamp":1680436595878},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1995,11,1]],"date-time":"1995-11-01T00:00:00Z","timestamp":815184000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1995,11]]},"DOI":"10.1007\/bf01592243","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T20:01:22Z","timestamp":1114718482000},"page":"29-50","source":"Crossref","is-referenced-by-count":4,"title":["One-third-integrality in the max-cut problem"],"prefix":"10.1007","volume":"71","author":[{"given":"Monique","family":"Laurent","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Svatopluk","family":"Poljak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/S0167-5060(08)70876-8","volume-title":"Combinatorics 79, Part I, Annals of Discrete Mathematics, Vol. 8","author":"D. Avis","year":"1980","unstructured":"D. Avis, \u201cExtremal metrics induced by graphs,\u201d in: M. Deza and I.G. Rosenberg, eds.,Combinatorics 79, Part I, Annals of Discrete Mathematics, Vol. 8 (North-Holland, Amsterdam, 1980) pp. 217\u2013220."},{"issue":"1","key":"CR2","doi-asserted-by":"crossref","first-page":"126","DOI":"10.4153\/CJM-1980-010-0","volume":"32","author":"D. Avis","year":"1980","unstructured":"D. Avis, \u201cOn the extreme rays of the metric cone,\u201dCanadian Journal of Mathematics 32 (1) (1980) 126\u2013144.","journal-title":"Canadian Journal of Mathematics"},{"issue":"1","key":"CR3","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/BF01580600","volume":"60","author":"F. Barahona","year":"1993","unstructured":"F. Barahona, \u201cOn cuts and matchings in planar graphs,\u201dMathematical Programming 60 (1) (1993) 53\u201368.","journal-title":"Mathematical Programming"},{"issue":"2","key":"CR4","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02592023","volume":"36","author":"F. Barahona","year":"1986","unstructured":"F. Barahona and A.R. Mahjoub, \u201cOn the cut polytope,\u201dMathematical Programming 36 (2) (1986) 157\u2013173.","journal-title":"Mathematical Programming"},{"key":"CR5","first-page":"205","volume-title":"Applied Geometry and Discrete Mathematics\u2014The Victor Klee Festschrift, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 4","author":"M. Deza","year":"1991","unstructured":"M. Deza, V.P. Grishukhin and M. Laurent, \u201cThe symmetries of the cut polytope and of some relatives,\u201d in: P. Gritzman and B. Sturmfels, eds.,Applied Geometry and Discrete Mathematics\u2014The Victor Klee Festschrift, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 4 (American Mathematical Society, Providence, RI, 1991) pp. 205\u2013220."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF02350631","volume":"8","author":"M. Deza","year":"1992","unstructured":"M. Deza, M. Laurent and S. Poljak, \u201cThe cut cone III: on the role of triangle facets,\u201dGraphs and Combinatorics 8 (1992) 125\u2013142; (updated version:Graphs and Combinatorics 9 (1993) 135\u2013152).","journal-title":"Graphs and Combinatorics"},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"A.M.H. Gerards and M. Laurent, \u201cA characterization of box 1\/d-integral binary clutters,\u201dJournal of Combinatorial Theory B 65 (1995).","DOI":"10.1006\/jctb.1995.1050"},{"key":"CR8","first-page":"422","volume-title":"Proceedings of the 26th Annual ACM Symposium on the Theory of Computing","author":"M.X. Goemans","year":"1994","unstructured":"M.X. Goemans and D.P. Williamson, \u201c0.878-approximation algorithms for MAX CUT and MAX 2SAT,\u201d in:Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (Association for Computing Machinery, New York, 1994) pp. 422\u2013431."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0195-6698(92)90021-Q","volume":"13","author":"V.P. Grishukhin","year":"1992","unstructured":"V.P. Grishukhin, \u201cComputing extreme rays of the metric cone for seven points,\u201dEuropean Journal of Combinatorics 13 (1992) 153\u2013165.","journal-title":"European Journal of Combinatorics"},{"key":"CR10","first-page":"129","volume":"13","author":"M. Iri","year":"1970\u20131971","unstructured":"M. Iri, \u201cOn an extension of the maximum-flow minimum-cut theorem to multicommodity flows,\u201dJournal of the Operations Research Society of Japan 13 (1970\u20131971) 129\u2013135.","journal-title":"Journal of the Operations Research Society of Japan"},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"M. Laurent, \u201cGraphic vertices of the metric polytope,\u201dDiscrete Mathematics, to appear.","DOI":"10.1016\/0012-365X(94)00091-V"},{"key":"CR12","first-page":"274","volume-title":"Integer Programming and Combinatorial Optimization","author":"M. Laurent","year":"1992","unstructured":"M. Laurent and S. Poljak, \u201cThe metric polytope,\u201d in: E. Balas, G. Cornuejols and R. Kannan, eds.,Integer Programming and Combinatorial Optimization (GSIA, Carnegie-Mellon University, Pittsburgh, PA, 1992) pp. 274\u2013286."},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"M. Laurent and S. Poljak, \u201cOn a positive semidefinite relaxation of the cut polytope,\u201dLinear Algebra and its Applications 223\u2013224 (1995) 439\u2013461.","DOI":"10.1016\/0024-3795(95)00271-R"},{"issue":"1","key":"CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(85)90004-6","volume":"11","author":"M.V. Lomonosov","year":"1985","unstructured":"M.V. Lomonosov, \u201cCombinatorial approaches to multiflow problems,\u201dDiscrete Applied Mathematics 11 (1) (1985) 1\u201393.","journal-title":"Discrete Applied Mathematics"},{"key":"CR15","first-page":"569","volume-title":"Sets, Graphs and Numbers, Budapest, 1991, Colloquia Mathematica Societatis J\u00e1nos Bolyai, Vol. 60","author":"S. Poljak","year":"1992","unstructured":"S. Poljak, \u201cPolyhedral and eigenvalue approximations of the max-cut problem,\u201d in:Sets, Graphs and Numbers, Budapest, 1991, Colloquia Mathematica Societatis J\u00e1nos Bolyai, Vol. 60 (North-Holland, Amsterdam, 1992) pp. 569\u2013581."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0167-6377(94)90068-X","volume":"16","author":"S. Poljak","year":"1994","unstructured":"S. Poljak and Zs. Tuza, \u201cThe expected error of the polyhedral approximation of the max-cut problem,\u201dOperations Research Letters 16 (1994) 191\u2013198.","journal-title":"Operations Research Letters"},{"key":"CR17","unstructured":"N. Robertson and P.D. Seymour, \u201cGraph minors XX. Wagner's conjecture,\u201d Preprint (1988)."},{"key":"CR18","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0012-365X(93)90517-W","volume":"113","author":"W. Schw\u00e4rzler","year":"1993","unstructured":"W. Schw\u00e4rzler and A. Seb\u0151, \u201cA generalized cut-condition for multiflows in matroids,\u201dDiscrete Mathematics 113 (1993) 207\u2013221.","journal-title":"Discrete Mathematics"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0095-8956(77)90031-4","volume":"23","author":"P.D. Seymour","year":"1977","unstructured":"P.D. Seymour, \u201cThe matroids with the max-flow min-cut property,\u201dJournal of Combinatorial Theory B 23 (1977) 189\u2013222.","journal-title":"Journal of Combinatorial Theory B"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S0195-6698(81)80033-9","volume":"2","author":"P.D. Seymour","year":"1981","unstructured":"P.D. Seymour, \u201cMatroids and multicommodity flows,\u201dEuropean Journal of Combinatorics 2 (1981) 257\u2013290.","journal-title":"European Journal of Combinatorics"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01592243.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01592243\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01592243","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T04:17:29Z","timestamp":1586233049000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01592243"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,11]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,11]]}},"alternative-id":["BF01592243"],"URL":"https:\/\/doi.org\/10.1007\/bf01592243","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,11]]}}}