Stronger linear programming relaxations of max-cut

DOI10.1007/S10107-003-0423-5MaRDI QIDQ1403298zbMATH OpenOpenAlexFDO

Authors David Avis, Jun Umemoto

Publication date 1 September 2003

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

Full work available at URL https://doi.org/10.1007/s10107-003-0423-5

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Recommendations

• Linear programming relaxations of \textsc{maxcut}
• Strengthened semidefinite programming relaxations for the max-cut problem.
• On the integrality ratio of semidefinite relaxations of MAX CUT
• The expected relative error of the polyhedral approximation of the max- cut problem
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem

Cited in

(21)

• Lifting inequalities: a framework for generating strong cuts for nonlinear programs
• Spectral bounds for the maximum cut problem
• scientific article; zbMATH DE number 4068611 (Why is no real title available?)
• Complexity results for the gap inequalities for the max-cut problem
• A polyhedral approach to the single row facility layout problem
• Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results
• A guide to conic optimisation and its applications
• A semidefinite programming based polyhedral cut and price approach for the maxcut problem
• Gap inequalities for non-convex mixed-integer quadratic programs
• Sherali-Adams strikes back
• Ramsey theory and integrality gap for the independent set problem
• Exploring the relationship between max-cut and stable set relaxations
• On the linear relaxation of the \(s-t\)-cut problem with budget constraints
• Binary positive semidefinite matrices and associated integer polytopes
• The Boolean quadric polytope
• Linear programming relaxations of \textsc{maxcut}
• Metric-Constrained Optimization for Graph Clustering Algorithms
• Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
• The expected relative error of the polyhedral approximation of the max- cut problem
• Gap inequalities for the max-cut problem: a cutting-plane algorithm
• Binary Positive Semidefinite Matrices and Associated Integer Polytopes

Describes a project that uses

Uses Software

• SDPA

This page was built for publication: Stronger linear programming relaxations of max-cut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1403298)