Faster exact solution of sparse MaxCut and QUBO problems

The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems-by using mathematical … Read more

Solving maximum cut problems by simulated annealing

This paper gives a straightforward implementation of simulated annealing for solving maximum cut problems and compares its performance to that of some existing heuristic solvers. The formulation used is classical, dating to a 1989 paper of Johnson, Aragon, McGeoch, and Schevon. This implementation uses no structure peculiar to the maximum cut problem, but its low … Read more

Improved lower bounds for the 2-page crossing numbers of K(m,n) and K(n) via semidefinite programming

The crossing number of a graph is the minimal number of edge crossings achievable in a drawing of the graph in the plane. The crossing numbers of complete and complete bipartite graphs are long standing open questions. In a 2-page drawing of a graph, all vertices are drawn on a circle, and no edge may … Read more

Row by row methods for semidefinite programming

We present a row-by-row (RBR) method for solving semidefinite programming (SDP) problem based on solving a sequence of problems obtained by restricting the n-dimensional positive semidefinite constraint on the matrix X. By fixing any (n-1)-dimensional principal submatrix of X and using its (generalized) Schur complement, the positive semidefinite constraint is reduced to a simple second-order … Read more