The expected relative error of the polyhedral approximation of the max- cut problem

DOI10.1016/0167-6377(94)90068-XzbMath0823.90129OpenAlexW1985142495MaRDI QIDQ1892101

Zsolt Tuza, Svatopluk Poljak

Publication date: 25 October 1995

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(94)90068-x

zbMATH Keywords

random graphlinear relaxationmax-cut problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

The Boolean Quadric Polytope, One-third-integrality in the max-cut problem, Small bipartite subgraph polytopes, A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems, A guide to conic optimisation and its applications, Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems, A semidefinite programming based polyhedral cut and price approach for the maxcut problem, Spectral bounds for the maximum cut problem, Sherali-adams strikes back, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes, Unnamed Item, Node and edge relaxations of the max-cut problem, Metric-Constrained Optimization for Graph Clustering Algorithms

Cites Work

• Experiments in quadratic 0-1 programming
• Laplacian eigenvalues and the maximum cut problem
• Node and edge relaxations of the max-cut problem
• The spectrum of \(\lambda\)-times repeated blocks for \(\text{TS}(v,\lambda)\)
• Solving the max-cut problem using eigenvalues
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Linear-Time Approximation Algorithms for the Max Cut Problem
• On the cut polytope
• The cut cone. III: On the role of triangle facets
• Unnamed Item
• Unnamed Item
• Unnamed Item