Title
Improved Approximation Algorithms for Orthogonally Constrained Problems Using Semidefinite Optimization
Abstract
Building on the blueprint from Goemans and Williamson (1995) for the Max-Cut problem, we construct a polynomial-time approximation scheme for orthogonally constrained quadratic optimization problems. First, we derive a semidefinite relaxation and propose a randomized rounding algorithm to generate feasible solutions from the relaxation. Second, we derive purely multiplicative approximation guarantees for our algorithm. When optimizing for m orthogonal vectors in dimension n, we show that our algorithm achieves a performance ratio of at least 1/π(log(2m)+1). Our analysis is tight in the sense that we elicit instances where our algorithm’s performance is at most O(1/ logm). We also show how to compute a tighter constant for finite (n,m) by solving a univariate optimization problem, and show that this analysis is exact for any n when m = 1.
Bio
Jean is an Assistant Professor of Management Science and Operations at London Business School. His research focuses on discrete optimization, robust optimization, and machine learning, with applications to healthcare and sustainable operations. His work has been published in journals like Operations Research, Management Science, Mathematical Programming, and Journal of Machine Learning Research, and recognized by many awards, including the POMS College of Healthcare Operations Management and INFORMS Pierskalla awards, the M&SOM Data-Driven Challenge competition, and the George E. Nicholson best student paper award. He holds a PhD in Operations Research from MIT.