{"id":"arxiv/2607.29386","url":"https://arxiv.org/abs/2607.29386","tags":["math.OC","cs.DM"],"score":0,"title":"Rational Jacobi Rotations and the Complexity of Approximating Mixed Integer Quadratic Programming","domain":"math.OC","source":"arxiv","authors":["Alberto Del Pia"],"reviews":0,"subject":"math.OC","summary":"We present an algorithm that finds an epsilon-approximate solution to a mixed integer quadratic programming (MIQP) problem, and that runs on a Turing machine in time polynomial in the size of the instance and in 1/epsilon, provided that the number of integer variables and the number of negative eigenvalues of the Hessian of the objective function are fixed. Unless P=NP, both restrictions are necessary, so this completes the characterization of the complexity of approximating MIQP in terms of the number of integer variables and the inertia of the Hessian; the result is new already in the…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-31","reactions":{}}