Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1505.06840 · Operations Research Letters

A MAX-CUT formulation of 0/1 programs

Jean Bernard Lasserre

Published Dec 29, 2015• 31 citations
arXivHTMLPDF
DOI
10.1016/j.orl.2015.12.014

Related papers

Almost optimal classical algorithms for a quantum generalization of Max Cut.

Ojas Parekh

•Jul 30, 2020•0 citations

Semidefinite programming approaches for stable set and max-cut problems

Lennart Sinjorgo

This thesis investigates the use of semidefinite programming (SDP) for solving (variants of) the well-known stable set and max-cut problems. Chapter 2 considers a generalization of the stable set problem, and a corresponding SDP relaxation. Similarly, Chapter 3 considers a generalization of the max-cut problem that involves complex roots of unity. Various complex SDP relaxations of this generalized max-cut problem are studied. Chapter 4 provides approximation algorithms for the quantum generalization of the max-cut problem. These approximation algorithms employ a hierarchy of SDP relaxations for noncommutative polynomial optimization problems. Chapter 5 provides an SDP algorithm for computing bounds on the stability numbers of graphs. Chapter 6 provides an SDP algorithm for solving the MAX-SAT problem. Chapters 5 and 6 provide extensive numerical results on these algorithms.

•Jan 20, 2026•0 citations

Experiments in quadratic 0–1 programming

Francisco Barahona, Michael Jünger, Gerhard Reinelt

Mathematical Programming•May 1, 1989•196 citations

The Effectiveness of Classical and Hybrid Models for MaxCut problem

L. Lavagna, F. De Falco, M. Panella

•Jan 1, 2025•0 citations

A Dataless Reinforcement Learning Approach to Rounding Hyperplane Optimization for Max-Cut

Gabriel Maliakal, Ismail Alkhouri, Alvaro Velasquez +2 more

The Maximum Cut (MaxCut) problem is NP-Complete, and obtaining its optimal solution is NP-hard in the worst case. As a result, heuristic-based algorithms are commonly used, though their design often requires significant domain expertise. More recently, learning-based methods trained on large (un)labeled datasets have been proposed; however, these approaches often struggle with generalizability and scalability. A well-known approximation algorithm for MaxCut is the Goemans-Williamson (GW) algorithm, which relaxes the Quadratic Unconstrained Binary Optimization (QUBO) formulation into a semidefinite program (SDP). The GW algorithm then applies hyperplane rounding by uniformly sampling a random hyperplane to convert the SDP solution into binary node assignments. In this paper, we propose a training-data-free approach based on a non-episodic reinforcement learning formulation, in which an agent learns to select improved rounding hyperplanes that yield better cuts than those produced by the GW algorithm. By optimizing over a Markov Decision Process (MDP), our method consistently achieves better cuts across large-scale graphs with varying densities and degree distributions.

arXiv:2505.13405•May 19, 2025•0 citations

Solving mixed 0-1programs by a lift-and-project method

Egon Balas, Sabastián Ceria, Gérard Cornuéjols

Symposium on Discrete Algorithms•Jan 1, 1993•16 citations
This thesis investigates the use of semidefinite programming (SDP) for solving (variants of) the well-known stable set and max-cut problems. Chapter 2 considers a generalization of the stable set problem, and a corresponding SDP relaxation. Similarly, Chapter 3 considers a generalization of the max-cut problem that involves complex roots of unity. Various complex SDP relaxations of this generalized max-cut problem are studied. Chapter 4 provides approximation algorithms for the quantum generalization of the max-cut problem. These approximation algorithms employ a hierarchy of SDP relaxations for noncommutative polynomial optimization problems. Chapter 5 provides an SDP algorithm for computing bounds on the stability numbers of graphs. Chapter 6 provides an SDP algorithm for solving the MAX-SAT problem. Chapters 5 and 6 provide extensive numerical results on these algorithms.
The Maximum Cut (MaxCut) problem is NP-Complete, and obtaining its optimal solution is NP-hard in the worst case. As a result, heuristic-based algorithms are commonly used, though their design often requires significant domain expertise. More recently, learning-based methods trained on large (un)labeled datasets have been proposed; however, these approaches often struggle with generalizability and scalability. A well-known approximation algorithm for MaxCut is the Goemans-Williamson (GW) algorithm, which relaxes the Quadratic Unconstrained Binary Optimization (QUBO) formulation into a semidefinite program (SDP). The GW algorithm then applies hyperplane rounding by uniformly sampling a random hyperplane to convert the SDP solution into binary node assignments. In this paper, we propose a training-data-free approach based on a non-episodic reinforcement learning formulation, in which an agent learns to select improved rounding hyperplanes that yield better cuts than those produced by the GW algorithm. By optimizing over a Markov Decision Process (MDP), our method consistently achieves better cuts across large-scale graphs with varying densities and degree distributions.