10 papers
Rational Jacobi Rotations and the Complexity of Approximating Mixed Integer Quadratic Programming
Alberto Del Pia
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 complete edge relaxation for binary polynomial optimization
Alberto Del Pia, Aida Khajavirad
We consider the multilinear polytope, defined as the convex hull of the feasible region of a lifted binary polynomial optimization problem. We define a relaxation in an extended sp…
A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation
Alberto Del Pia, Dekun Zhou
Sparse Principal Component Analysis (SPCA) is a fundamental technique for dimensionality reduction, and is NP-hard. In this paper, we introduce a randomized approximation algorithm…
Projection-width as a structural parameter for discrete separable optimization
Alberto Del Pia
While several classes of integer linear optimization problems are known to be solvable in polynomial time, far fewer tractability results exist for integer nonlinear optimization.…
Towards a geometric characterization of unbounded integer cubic optimization problems via thin rays
Alberto Del Pia
We study geometric characterizations of unbounded integer polynomial optimization problems. While unboundedness along a ray fully characterizes unbounded integer linear and quadrat…
An SDP Relaxation for the Sparse Integer Least Squares Problem
Alberto Del Pia, Dekun Zhou
In this paper, we study the \emph{sparse integer least squares problem} (SILS), an NP-hard variant of least squares with sparse -vectors. We propose an -based…