From Graph Orientation to the Unweighted Maximum Cut

DOI10.1007/978-3-319-42634-1_30zbMath1476.68192OpenAlexW2492335092MaRDI QIDQ2817879

Antoine Glorieux, Walid Ben-Ameur, José Neto

Publication date: 2 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-42634-1_30

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Mixed integer programming (90C11) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)

Uses Software

• Biq Mac

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems
• Weakly bipartite graphs and the max-cut problem
• Using domain decomposition to find graph bisectors
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• A gradient-based randomised heuristic for the maximum cut problem
• Improved semidefinite bounding procedure for solving max-cut problems to optimality
• Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
• Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lovász--Schrijver Lift-and-Project Procedure
• Spectral bounds for the maximum cut problem
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Improved Linear Integer Programming Formulations of Nonlinear Integer Problems
• P-Complete Approximation Problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Randomized heuristics for the Max-Cut problem
• On the cut polytope
• Some Network Flow Problems Solved with Pseudo-Boolean Programming
• Some optimal inapproximability results
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• Geometry of cuts and metrics

This page was built for publication: From Graph Orientation to the Unweighted Maximum Cut