Cover Image

On exactness of SDP relaxation for the maximum cut problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bhardwaj, Avinash, Gogoi, Hritiz, Narayanan, Vishnu, Pathapati, Abhishek
Format:	Preprint
Published:	2025
Subjects:	Optimization and Control 90C27, 90C22, 90C35
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On generators of $k$-PSD closures of the positive semidefinite cone
by: Bhardwaj, Avinash, et al.
Published: (2024)

SDP Approach to Quadratic Vertex-Disjoint Paths Problem
by: Xu, Mingming, et al.
Published: (2026)

Exact augmented Lagrangian duality for mixed integer convex optimization
by: Bhardwaj, Avinash, et al.
Published: (2022)

Edge expansion of a graph: SDP-based computational strategies
by: Gupte, Akshay, et al.
Published: (2024)

SDP bounds on the stability number via ADMM and intermediate levels of the Lasserre hierarchy
by: Sinjorgo, Lennart, et al.
Published: (2025)

Improved semidefinite programming bounds for the maximum $k$-colorable subgraph problem
by: Barkel, Mathijs, et al.
Published: (2026)

Strong SDP based bounds on the cutwidth of a graph
by: Gaar, Elisabeth, et al.
Published: (2023)

Exact SDP relaxations for a class of quadratic programs with finite and infinite quadratic constraints
by: Arima, Naohiko, et al.
Published: (2024)

The exact subgraph hierarchy and its vertex-transitive variant for the stable set problem for Paley graphs
by: Gaar, Elisabeth, et al.
Published: (2024)

A Computational Search for Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy
by: Au, Yu Hin, et al.
Published: (2025)

A more efficient reformulation of complex SDP as real SDP
by: Wang, Jie
Published: (2023)

Separable QCQPs and Their Exact SDP Relaxations
by: Kojima, Masakazu, et al.
Published: (2026)

Practical Experience with Stable Set and Coloring Relaxations
by: Pucher, Dunja, et al.
Published: (2024)

Constructing QCQP Instances Equivalent to Their SDP Relaxations
by: Kojima, Masakazu, et al.
Published: (2025)

Benchmarking of quantum and classical SDP relaxations for QUBO formulations of real-world logistics problems
by: Ostermann, Birte, et al.
Published: (2025)

Projection, Degeneracy, and Singularity Degree for Spectrahedra
by: Im, Haesol, et al.
Published: (2024)

A Canceling Heuristic for the Directed Traveling Salesman Problem
by: Borgwardt, Steffen, et al.
Published: (2026)

Exploring chordal sparsity in semidefinite programming with sparse plus low-rank data matrices
by: Tang, Tianyun, et al.
Published: (2024)

A Low-rank Augmented Lagrangian Method for Polyhedral-SDP and Moment-SOS Relaxations of Polynomial Optimization
by: Hou, Di, et al.
Published: (2025)

Relaxations of KKT Conditions do not Strengthen Finite RLT and SDP-RLT Bounds for Nonconvex Quadratic Programs
by: Yildirim, E. Alper
Published: (2025)

Stable Set Polytopes with Rank $|V(G)|/3$ for the Lovász--Schrijver SDP Operator
by: Au, Yu Hin, et al.
Published: (2025)

Duality attainment and strict feasibility of the generalized moment problem and its relaxations
by: Halaseh, Sami, et al.
Published: (2026)

On different Versions of the Exact Subgraph Hierarchy for the Stable Set Problem
by: Gaar, Elisabeth
Published: (2020)

T-semidefinite programming relaxation with third-order tensors for constrained polynomial optimization
by: Marumo, Hiroki, et al.
Published: (2024)

Semidefinite approximations for bicliques and biindependent pairs
by: Laurent, Monique, et al.
Published: (2023)

Benign landscapes of low-dimensional relaxations for orthogonal synchronization on general graphs
by: McRae, Andrew D., et al.
Published: (2023)

Computational complexity of sum-of-squares bounds for copositive programs
by: Palomba, Marilena, et al.
Published: (2025)

Tighter yet more tractable relaxations and nontrivial instance generation for sparse standard quadratic optimization
by: Bomze, Immanuel, et al.
Published: (2024)

Exact Solutions for the NP-hard Wasserstein Barycenter Problem using a Doubly Nonnegative Relaxation and a Splitting Method
by: Jung, Woosuk L., et al.
Published: (2023)

A low-rank augmented Lagrangian method for doubly nonnegative relaxations of mixed-binary quadratic programs
by: Hou, Di, et al.
Published: (2025)

Evacuation Planning on Time-Expanded Networks with Integrated Wildfire Information
by: Borgwardt, Steffen, et al.
Published: (2024)

Non-convex relaxation and 1/2-approximation algorithm for the chance-constrained binary knapsack problem
by: Kim, Junyoung, et al.
Published: (2024)

Real-time solution of quadratic optimization problems with banded matrices and indicator variables
by: Gomez, Andres, et al.
Published: (2024)

Beyond binarity: Semidefinite programming for ternary quadratic problems
by: de Meijer, Frank, et al.
Published: (2026)

Second-order sequential optimality conditions for nonlinear semidefinite optimization problems
by: Li, Huimin, et al.
Published: (2025)

A preconditioned augmented Lagrangian method for solving semidefinite programming problems
by: Tang, Tianyun, et al.
Published: (2026)

Finding Short Paths on Simple Polytopes
by: Black, Alexander E., et al.
Published: (2026)

Structural Insights and an IP-based Solution Method for Patient-to-room Assignment under Consideration of Single Room Entitlements
by: Brandt, Tabea, et al.
Published: (2023)

Adjustable Robust Nonlinear Network Design Without Controllable Elements under Load Scenario Uncertainties
by: Thürauf, Johannes, et al.
Published: (2024)

Metaheuristic algorithms for the induced P-median problem with upgrades
by: Salazar, Sergio, et al.
Published: (2026)