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:2308.01361 · Operations Research Letters

On relaxations of the max k-cut problem formulations

Ramin Fakhimi, Hamidreza Validi, Illya V. Hicks, Tamás Terlaky B, Luis F. Zuluaga

Published Aug 8, 2023• 3 citations
arXivHTMLPDF
DOI
10.1016/j.orl.2023.08.001

Related papers

Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation

Dachuan Xu, Shu-zhong Zhang

Science in China Series A Mathematics•Jul 30, 2007•7 citations

Solving SDP relaxations of Max-Cut problem with large number of hypermetric inequalities by L-BFGS-B

Timotej Hrga, Janez Povh

Optimization Letters•Nov 4, 2022•4 citations

Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations

Franz Rendl, Giovanni Rinaldi, Angelika Wiegele

Mathematical Programming•Jul 21, 2008•7 citations

A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations

Franz Rendl, Giovanni Rinaldi, Angelika Wiegele

Springer eBooks•Jun 25, 2007•55 citations

A MAX-CUT formulation of 0/1 programs

Jean Bernard Lasserre

arXiv:1505.06840•Operations Research Letters•Dec 29, 2015•32 citations

Solving General QUBOs with Warm-Start QAOA via a Reduction to Max-Cut

Bikrant Bhattacharyya, Michael Capriotti, Reuben Tate

The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm that finds approximate solutions to problems in combinatorial optimization, especially those that can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem. In prior work, researchers have considered various ways of "warm-starting" QAOA by constructing an initial quantum state using classically-obtained solutions or information; these warm-starts typically cause QAOA to yield better approximation ratios at much lower circuit depths. For the Max-Cut problem, one warm-start approaches constructs the initial state using the high-dimensional vectors that are output from an SDP relaxation of the corresponding Max-Cut problem. This work leverages these semidefinite warmstarts for a broader class of problem instances by using a standard reduction that transforms any QUBO instance into a Max-Cut instance. We empirically compare this approach to a "QUBO-relaxation" approach that relaxes the QUBO directly. Our results consider a variety of QUBO instances ranging from randomly generated QUBOs to QUBOs corresponding to specific problems such as the traveling salesman problem, maximum independent set, and portfolio optimization. We find that the best choice of warmstart approach is strongly dependent on the problem type.

arXiv:2504.06253•Apr 8, 2025•9 citations
The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm that finds approximate solutions to problems in combinatorial optimization, especially those that can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem. In prior work, researchers have considered various ways of "warm-starting" QAOA by constructing an initial quantum state using classically-obtained solutions or information; these warm-starts typically cause QAOA to yield better approximation ratios at much lower circuit depths. For the Max-Cut problem, one warm-start approaches constructs the initial state using the high-dimensional vectors that are output from an SDP relaxation of the corresponding Max-Cut problem. This work leverages these semidefinite warmstarts for a broader class of problem instances by using a standard reduction that transforms any QUBO instance into a Max-Cut instance. We empirically compare this approach to a "QUBO-relaxation" approach that relaxes the QUBO directly. Our results consider a variety of QUBO instances ranging from randomly generated QUBOs to QUBOs corresponding to specific problems such as the traveling salesman problem, maximum independent set, and portfolio optimization. We find that the best choice of warmstart approach is strongly dependent on the problem type.