Best Principal Submatrix Selection for the Maximum Entropy Sampling Problem Scalable Algorithms and Performance Guarantees
This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix of a prespecified size from a covariance matrix. MESP has been widely applied to many areas, including healthcare, power system, manufacturing, and data science. We derive a novel convex integer program for MESP and show that its continuous relaxation yields a near-optimal solution. The results motivate us to study an efficient sampling algorithm and develop its approximation bound for MESP, which improves the best-known bound in the literature. We then provide an efficient deterministic implementation of the sampling algorithm with the same approximation bound. By developing new mathematical tools for the singular matrices and analyzing the Lagrangian dual of the proposed convex integer program, we investigate the widely-used local search algorithm and prove its first-known approximation bound for MESP.
Speaker: Prof. Weijun XIE
Date: 27 Jan 2026 (Tuesday)
Time: 9:30am – 10:30am
Venue: LAU 6-209
Poster: Click here
Biography
Prof. Weijun XIE is an Associate Professor in the H. Milton Stewart School of Industrial and Systems Engineering at the Georgia Institute of Technology. His research focuses on mixed-integer optimization, stochastic optimization, and data-driven decision-making, with applications in machine learning, logistics, and energy systems. His work has been recognized with multiple awards, including the 2021 NSF CAREER Award, the 2025 INFORMS Freight Transportation and Logistics SIG Award, an Honorable Mention for the 2025 INFORMS Computing Society Prize, and the 2020 INFORMS Young Researchers Paper Prize. He currently serves as an Associate Editor for Operations Research, Mathematical Programming, Naval Research Logistics, and the Journal of Global Optimization.