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

DOI10.1016/0167-6377(94)90068-XMaRDI QIDQ1892101zbMATH OpenOpenAlexFDO

Authors Svatopluk Poljak, Zsolt Tuza

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)

Recommendations

• A probabilistic result for the max-cut problem on random graphs
• Stronger linear programming relaxations of max-cut
• scientific article; zbMATH DE number 426360
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• On the approximability of Max-Cut

Cites work

• scientific article; zbMATH DE number 426360 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 878334 (Why is no real title available?)
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Experiments in quadratic 0-1 programming
• Laplacian eigenvalues and the maximum cut problem
• Linear-Time Approximation Algorithms for the Max Cut Problem
• Node and edge relaxations of the max-cut problem
• On the cut polytope
• Solving the max-cut problem using eigenvalues
• The cut cone. III: On the role of triangle facets
• The spectrum of \(\lambda\)-times repeated blocks for \(\text{TS}(v,\lambda)\)

Cited in

(15)

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

This page was built for publication: The expected relative error of the polyhedral approximation of the max- cut problem

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