One-third-integrality in the max-cut problem

DOI10.1007/BF01592243zbMath0855.90133OpenAlexW2086486273MaRDI QIDQ1924057

Svatopluk Poljak, Monique Laurent

Publication date: 3 February 1997

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01592243

zbMATH Keywords

cut polytopeforbidden minorlinear relaxationmax-cut problemmetric polytopeseries parallel graphsbox one-third-integralityone-third-integrality

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

Graphic vertices of the metric polytope, Lifting and separation procedures for the cut polytope, A counterexample to the dominating set conjecture, The real positive semidefinite completion problem for series-parallel graphs, Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On cuts and matchings in planar graphs
• Graph minors. XX: Wagner's conjecture
• Combinatorial approaches to multiflow problems
• Matroids and multicommodity flows
• Computing extreme rays of the metric cone for seven points
• The matroids with the max-flow min-cut property
• The expected relative error of the polyhedral approximation of the max- cut problem
• On a positive semidefinite relaxation of the cut polytope
• A characterization of box \(\frac 1d\)-integral binary clutters
• Graphic vertices of the metric polytope
• A generalized cut-condition for multiflows in matroids
• On the Extreme Rays of the Metric Cone
• Extremal Metrics Induced by Graphs
• On the cut polytope
• The cut cone. III: On the role of triangle facets