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