Node and edge relaxations of the max-cut problem

DOI10.1007/BF02238072zbMath0807.90099OpenAlexW129046272MaRDI QIDQ1319044

V. Pereyra

Publication date: 12 April 1994

Published in: Computing (Search for Journal in Brave)

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

zbMATH Keywords

nonsmooth optimizationupper boundsemidefinite programmingmax- cut problemmin-max eigenvalue problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Combinatorial optimization (90C27)

Related Items

The expected relative error of the polyhedral approximation of the max- cut problem, On a positive semidefinite relaxation of the cut polytope, Solving the max-cut problem using eigenvalues, Laplace eigenvalues of graphs---a survey, Semidefinite programming and combinatorial optimization, Path optimization for graph partitioning problems, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes

Cites Work

• The max-cut problem on graphs not contractible to \(K_ 5\)
• Experiments in quadratic 0-1 programming
• Laplacian eigenvalues and the maximum cut problem
• The expected relative error of the polyhedral approximation of the max- cut problem
• Solving the max-cut problem using eigenvalues
• Computational aspects of a branch and bound algorithm for quadratic zero- one programming
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• A Version of the Bundle Idea for Minimizing a Nonsmooth Function: Conceptual Idea, Convergence Analysis, Numerical Results
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item