CAREER: The Interplay between Combinatorial Optimization and Algorithmic Convex Geometry

University Of Washington, Seattle WA

Investigators

Abstract

Optimization problems, which look for the best solution satisfying given constraints, may arise in discrete settings, where there is a choice of a distinct set of possibilities like nodes in a graph, or continuous settings, where the choices are numbers that can be tuned with fine adjustments. Convex optimization problems are a special class in which the constraints are simple enough that continuous problems gain geometric and/or discrete structures. These structures have been studied extensively over the past century. Some of these techniques like linear programming have become fundamental tools in all fields of science. More recently, there have been interesting cases in which continuous methods have yielded advances in discrete optimization. In this project, the PI seeks to develop significantly more efficient algorithms to solve convex problems, especially problems come from graph and combinatorial problems. A major obstacle to developing nearly linear-time algorithms for both continuous and discrete problems is the lack of understanding of convex geometry and its connection to algorithms. This project focuses on three key topics and related goals: 1) Algorithmic Convex Geometry: understand how well convex sets can be approximated by ellipsoids (KLS conjecture), explore ways to deform an explicit given polytope as a Riemannian manifold and use the deformations to develop faster polytope sampling algorithms; 2) Combinatorial Optimization: break the square root iterations barrier for solving linear programming by understanding the relation between convex geometry and interior point methods to develop a fine-grained complexity for interior point methods; 3) Convex Optimization: investigate cutting plane methods via the geometry of localization sets, develop efficient cutting plane methods via algorithmic convex geometry and explore non-convex optimizations via sampling algorithms. Improved algorithms for optimization developed via this project through an improved understanding of these topics can have a broad impact across various sciences. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.