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

DOI10.1016/0167-6377(94)90068-XzbMATH Open0823.90129OpenAlexW1985142495MaRDI QIDQ1892101FDOQ1892101

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

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

zbMATH Keywords

random graphlinear relaxationmax-cut problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

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

Cited In (15)

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

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)