An experimental evaluation of semidefinite programming and spectral algorithms for max cut
From MaRDI portal
Publication:6579779
DOI10.1145/3609426MaRDI QIDQ6579779FDOQ6579779
Authors: Renee Mirka, David P. Williamson 
Publication date: 26 July 2024
Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)
Cites Work
- Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs
- TSPLIB—A Traveling Salesman Problem Library
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- BiqCrunch
- BiqBin: Moving Boundaries for NP-hard Problems by HPC
- Reducibility among Combinatorial Problems
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- A new algorithm for optimal 2-constraint satisfaction and its implications
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- Improved Analysis of a Max-Cut Algorithm Based on Spectral Partitioning
- P-Complete Approximation Problems
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Max Cut and the Smallest Eigenvalue
- Title not available (Why is that?)
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Title not available (Why is that?)
- An exact algorithm for MAX-CUT in sparse graphs
- New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree
- Path optimization for graph partitioning problems
- Greedy differencing edge-contraction heuristic for the max-cut problem
- What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO
- \texttt{MADAM}: a parallel exact solver for max-cut based on semidefinite programming and ADMM
This page was built for publication: An experimental evaluation of semidefinite programming and spectral algorithms for max cut
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6579779)
