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

Discrete Applied Mathematics

Bounds and fast approximation algorithms for binary quadratic optimization problems with application to MAX 2SAT

Hans van Maaren, Joost P. Warners

Published Dec 1, 2000• 3 citations
Publisher
DOI
10.1016/s0166-218x(00)00263-8

Related papers

An improved lower bound and approximation algorithm for binary constrained quadratic programming problem

Cheng Zhu Lu, Zhenbo Wang, Wenxun Xing

Journal of Global Optimization•Dec 17, 2009•6 citations

The Quadratic Unconstrained Binary Optimization Problem: Theory, Algorithms, and Applications

Springer eBooks•Jan 1, 2022•83 citations

A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)

Endre Boros, Peter L. Hammer, Richard L. Sun +1 more

Discrete Optimization•Dec 1, 2007•54 citations

Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs

Samuel Burer, Renato D. C. Monteiro, Yin Zhang

The Goemans--Williamson randomized algorithm guarantees a high-quality approximation to the MAX-CUT problem, but the cost associated with such an approximation can be excessively high for large-scale problems due to the need for solving an expensive semidefinite relaxation. In order to achieve better practical performance, we propose an alternative, rank-two relaxation and develop a specialized version of the Goemans--Williamson technique. The proposed approach leads to continuous optimization heuristics applicable to MAX-CUT as well as other binary quadratic programs, for example the MAX-BISECTION problem. A computer code based on the rank-two relaxation heuristics is compared with two state-of-the-art semidefinite programming codes that implement the Goemans--Williamson randomized algorithm, as well as with a purely heuristic code for effectively solving a particular MAX-CUT problem arising in physics. Computational results show that the proposed approach is fast and scalable and, more importantly, attains a higher approximation quality in practice than that of the Goemans--Williamson randomized algorithm. An extension to MAX-BISECTION is also discussed, as is an important difference between the proposed approach and the Goemans--Williamson algorithm; namely, that the new approach does not guarantee an upper bound on the MAX-CUT optimal value.

SIAM Journal on Optimization•Jan 1, 2002•229 citations

Design and FPGA Realization of QUBO hardware accelerator for MAX-CUT problem

Maciej Lewandowski, Piotr Dudek

Combinatorial optimization problems are fundamental to many industrial and scientific applications, but are often NP-hard, requiring heuristic and probabilistic approaches to find good solutions fast. This paper presents the first hardware implementation of the neuromorphic-inspired NeuroSA algorithm, for accelerating Quadratic Unconstrained Binary Optimization (QUBO) problems. We show that it is possible to run a standard QUBO benchmark problem with 800 variables on a low-cost FPGA with a clock speed of approximately 144 MHz, which converges to the same solution value found by the numerical solver.

IEEE International Symposium on Circuits and Systems proceedings•May 25, 2025•2 citations

Approximation Algorithm for A Mixed Binary Quadratically Constrained Quadratic Programming Problem

Zi Li Xu, Mingyi Hong

•Jan 1, 2015•1 citation
The Goemans--Williamson randomized algorithm guarantees a high-quality approximation to the MAX-CUT problem, but the cost associated with such an approximation can be excessively high for large-scale problems due to the need for solving an expensive semidefinite relaxation. In order to achieve better practical performance, we propose an alternative, rank-two relaxation and develop a specialized version of the Goemans--Williamson technique. The proposed approach leads to continuous optimization heuristics applicable to MAX-CUT as well as other binary quadratic programs, for example the MAX-BISECTION problem. A computer code based on the rank-two relaxation heuristics is compared with two state-of-the-art semidefinite programming codes that implement the Goemans--Williamson randomized algorithm, as well as with a purely heuristic code for effectively solving a particular MAX-CUT problem arising in physics. Computational results show that the proposed approach is fast and scalable and, more importantly, attains a higher approximation quality in practice than that of the Goemans--Williamson randomized algorithm. An extension to MAX-BISECTION is also discussed, as is an important difference between the proposed approach and the Goemans--Williamson algorithm; namely, that the new approach does not guarantee an upper bound on the MAX-CUT optimal value.
Combinatorial optimization problems are fundamental to many industrial and scientific applications, but are often NP-hard, requiring heuristic and probabilistic approaches to find good solutions fast. This paper presents the first hardware implementation of the neuromorphic-inspired NeuroSA algorithm, for accelerating Quadratic Unconstrained Binary Optimization (QUBO) problems. We show that it is possible to run a standard QUBO benchmark problem with 800 variables on a low-cost FPGA with a clock speed of approximately 144 MHz, which converges to the same solution value found by the numerical solver.