Small bipartite subgraph polytopes

DOI10.1016/j.orl.2010.05.004zbMath1231.05221OpenAlexW1979378096WikidataQ57702188 ScholiaQ57702188MaRDI QIDQ613319

Laura Galli, Adam N. Letchford

Publication date: 20 December 2010

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

Full work available at URL: https://eprints.lancs.ac.uk/id/eprint/45606/1/10.pdf

zbMATH Keywords

max-cut problempolyhedral combinatoricsintegrality ratios

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Structural characterization of families of graphs (05C75)

Related Items (1)

PANDA: a software for polyhedral transformations

Uses Software

• PORTA
• SMAPO

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weakly bipartite graphs and the max-cut problem
• Facets for the cut cone. I
• Laplacian eigenvalues and the maximum cut problem
• All facets of the cut cone \(C_ n\) for \(n=7\) are known
• The expected relative error of the polyhedral approximation of the max- cut problem
• Facets of the Bipartite Subgraph Polytope
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On the optimality of the random hyperplane rounding technique for MAX CUT
• The strongest facets of the acyclic subgraph polytope are unknown
• DECOMPOSITION AND PARALLELIZATION TECHNIQUES FOR ENUMERATING THE FACETS OF COMBINATORIAL POLYTOPES
• On the cut polytope
• The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁
• Geometry of cuts and metrics

This page was built for publication: Small bipartite subgraph polytopes