Integer least square problem

An SDP Relaxation for the Sparse Integer Least Square Problem

  • Alberto Del Pia
  • Dekun Zhou
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Semi-definite Programming Tags , , ,

    In this paper, we study the polynomial approximability or solvability of sparse integer least square problem (SILS), which is the NP-hard variant of the least square problem, where we only consider sparse {0, ±1}-vectors. We propose an l1-based SDP relaxation to SILS, and introduce a randomized algorithm for SILS based on the SDP relaxation. In … Read more