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 (7)

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

This page was built for publication: Node and edge relaxations of the max-cut problem