BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Weijun Xie (Virginia Tech) DTSTART:20200602T180000Z DTEND:20200602T183000Z DTSTAMP:20260423T021858Z UID:DOTs/11 DESCRIPTION:Title: Be st Submatrix Selection: Strong Formulations and Approximation Algorithms\nby Weijun Xie (Virginia Tech) as part of Discrete Optimization Talks\n \n\nAbstract\nMany interesting machine learning and data analytics problem s involve selecting the most informative principal submatix of of a prespe cified size from a covariance matrix\, such as maximum entropy sampling pr oblem\, experimental design\, sparse PCA. Although directly formulating th ese problems into mathematical programs is difficult\, we explore the Chol esky factorization of the original covariance matrix and recast the proble ms as mixed integer programs (MIPs). We also show that (i) these new MIPs usually have tight continuous relaxation bounds\, and (ii) by constructing dual solutions\, we can prove approximation bounds of the local search al gorithm. Our numerical experiments demonstrate that these approximation al gorithms can efficiently solve medium-sized and large-scale instances to n ear-optimality.\n LOCATION:https://researchseminars.org/talk/DOTs/11/ END:VEVENT END:VCALENDAR