AF: Small: New Approaches for Approximation and Online Algorithms

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

The area of approximation algorithms focuses on NP-hard optimization problems, and on obtaining fast algorithms that output solutions that are near-optimal, say in polynomial time. In the area of online algorithms, the input is revealed slowly over time, and the goal is to get good algorithms without knowing the future portions of the input. Many questions considered in this project are NP-hard, and often the resultant problems are not static problems but dynamic ones, hence these areas are central to algorithm design. This research project aims to develop new techniques in both these areas, to make progress on some long-standing open problems. For instance, it aims to develop general tools to solve convex optimization problems when the input appears online: given that convex optimization underlies many techniques in algorithms and machine learning, such results have broad applicability both within computer science and beyond. The research component of this project goes hand-in-hand with its educational and training component, which will include training both graduate and undergraduate students, and in developing new courses and materials. In this project, the goal is to bring together hitherto disparate techniques, and use their combination to solve some central questions. For instance, many NP-hard problems have been attacked using, on one hand, the tools of randomization and convex optimization, and on the other, the perspective of fixed-parameter tractability, where the algorithm is allowed to be exponential in some parameter. The project hopes to bring these areas together, and use this synthesis of ideas to further the state-of-the-art on the k-cut partitioning problems and k-means clustering problems, among others. This fine-grained notion of approximation algorithms should lead to new structural insights into these fundamental questions. In online algorithms, the hope is to use ideas from continuous optimization and online learning, in combination with the combinatorial ideas typically used in the design of online algorithms, to make progress on problems like k-server and online convex minimization. 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.