New bounds for the maximum cut problem

DOI10.1016/J.ENDM.2006.08.028MaRDI QIDQ3439502zbMATH OpenOpenAlexFDO

Authors Walid Ben-Ameur

Publication date 29 May 2007

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2006.08.028

zbMATH Keywords

eigen valueslower and upper boundsmaximum cutsemi definite programmingtight relaxations

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27)

Recommendations

• Spectral bounds for the maximum cut problem
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• The maximum cut problem
• scientific article; zbMATH DE number 780784
• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs

Cites work

• Combinatorial properties and the complexity of a max-cut approximation
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

Cited in

(7)

• Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality
• Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results
• The maximum cut problem on blow-ups of multiprojective spaces
• Sharpened lower bounds for cut elimination
• Tight Bounds for Gomory-Hu-like Cut Counting
• Finding Folkman Numbers via MAX CUT Problem
• Optimal Bounds for the k -cut Problem

This page was built for publication: New bounds for the maximum cut problem

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