4 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…
Factorized binary polynomial optimization
Alberto Del Pia
In binary polynomial optimization, the goal is to find a binary point maximizing a given polynomial function. In this paper, we propose a novel way of formulating this general opti…