We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. This class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A dequantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over stateoftheart algorithms. Such instances include approximating the ground state of spin glasses and MaxCut on ErdösRényi graphs. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into approximations of the original quadratic optimization problem.
more »
« less
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps
The traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization. Several semidefinite programming relaxations have been proposed recently that exploit a variety of mathematical structures including, for example, algebraic connectivity, permutation matrices, and association schemes. The main results of this paper are twofold. First, de Klerk and Sotirov [de Klerk E, Sotirov R (2012) Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry. Math. Programming 133(1):75–91.] present a semidefinite program (SDP) based on permutation matrices and symmetry reduction; they show that it is incomparable to the subtour elimination linear program but generally dominates it on small instances. We provide a family of simplicial TSP instances that shows that the integrality gap of this SDP is unbounded. Second, we show that these simplicial TSP instances imply the unbounded integrality gap of every SDP relaxation of the TSP mentioned in the survey on SDP relaxations of the TSP in section 2 of Sotirov [Sotirov R (2012) SDP relaxations for some combinatorial optimization problems. Anjos MF, Lasserre JB, eds., Handbook on Semidefinite, Conic and Polynomial Optimization (Springer, New York), 795–819.]. In contrast, the subtour linear program performs perfectly on simplicial instances. The simplicial instances thus form a natural litmus test for future SDP relaxations of the TSP.
more »
« less
 Award ID(s):
 1908517
 NSFPAR ID:
 10298221
 Date Published:
 Journal Name:
 Mathematics of Operations Research
 ISSN:
 0364765X
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Vygen, J ; Byrka, J (Ed.)One of the most famous conjectures in combinatorial optimization is the fourthirds conjecture, which states that the integrality gap of the subtour LP relaxation of the TSP is equal to $\frac43$. For 40 years, the best known upper bound was $1.5$. Recently, Karlin, Klein, and Oveis Gharan \cite{KKO21b} showed that the max entropy algorithm for the TSP gives an improved bound of $1.5  10^{36}$. In this paper, we show that the approximation ratio of the max entropy algorithm is at least 1.375, even for graphic TSP. Thus the max entropy algorithm does not appear to be the algorithm that will ultimately resolve the fourthirds conjecture in the affirmative, should that be possible.more » « less

Del Pia, Alberto ; Kaibel, Volker (Ed.)A longstanding conjecture for the traveling salesman problem (TSP) states that the integrality gap of the standard linear programming relaxation of the TSP (sometimes called the Subtour LP or the HeldKarp bound) is at most 4/3 for symmetric instances of the TSP obeying the triangle inequality. In this paper we consider the halfintegral case, in which a feasible solution to the LP has solution values in {0,1/2,1} . Karlin, Klein, and Oveis Gharan [9], in a breakthrough result, were able to show that in the halfintegral case, the integrality gap is at most 1.49993; Gupta et al. [6] showed a slight improvement of this result to 1.4983. Both of these papers consider a hierarchy of critical tight sets in the support graph of the LP solution, in which some of the sets correspond to cycle cuts and the others to degree cuts. Here we show that if all the sets in the hierarchy correspond to cycle cuts, then we can find a distribution of tours whose expected cost is at most 4/3 times the value of the halfintegral LP solution; sampling from the distribution gives us a randomized 4/3approximation algorithm. We note that known bad cases for the integrality gap have a gap of 4/3 and have a halfintegral LP solution in which all the critical tight sets in the hierarchy are cycle cuts; thus our result is tight.more » « less

We develop techniques to convexify a set that is invariant under permutation and/or change of sign of variables and discuss applications of these results. First, we convexify the intersection of the unit ball of a permutation and signinvariant norm with a cardinality constraint. This gives a nonlinear formulation for the feasible set of sparse principal component analysis (PCA) and an alternative proof of the Ksupport norm. Second, we characterize the convex hull of sets of matrices defined by constraining their singular values. As a consequence, we generalize an earlier result that characterizes the convex hull of rankconstrained matrices whose spectral norm is below a given threshold. Third, we derive convex and concave envelopes of various permutationinvariant nonlinear functions and their level sets over hypercubes, with congruent bounds on all variables. Finally, we develop new relaxations for the exterior product of sparse vectors. Using these relaxations for sparse PCA, we show that our relaxation closes 98% of the gap left by a classical semidefinite programming relaxation for instances where the covariance matrices are of dimension up to 50 × 50.more » « less

Columnsparse packing problems arise in several contexts in both deterministic and stochastic discrete optimization. We present two unifying ideas, (nonuniform) attenuation and multiplechance algorithms, to obtain improved approximation algorithms for some wellknown families of such problems. As three main examples, we attain the integrality gap, up to lowerorder terms, for known LP relaxations for kcolumn sparse packing integer programs (Bansal et al., Theory of Computing, 2012) and stochastic kset packing (Bansal et al., Algorithmica, 2012), and go “half the remaining distance” to optimal for a major integralitygap conjecture of Furedi, Kahn and Seymour on hypergraph matching (Combinatorica, 1993).more » « less