CAREER: Modern Algorithm Design via the Optimization Lens

点击翻译按钮获取中文摘要

Computer Science is a rapidly growing field leading to new kinds of computational problems. For example, data is being produced at a huge rate today, and an algorithm's access to it is restricted either due to sheer volume or due to ownership concerns. This forces designers to revisit classical algorithms. In machine learning, one uses clustering algorithms to learn about unlabeled data. However, the presence of noise and anomalies can distort this, and one needs good outlier-detection algorithms. The goal of this project is to use and enhance techniques from mathematical optimization to tackle these new algorithmic challenges. In doing so, the project will create unified methodologies to attack problems arising in different areas. In turn, these news ideas will also lead to answers to classical optimization problems. Work on this project will go hand-in-hand with the creation of relevant courses in undergraduate and graduate curriculum which focus on these new algorithmic insights. The educational component of this project also includes a plan for injecting computer science and algorithmic thinking into the K-12 system. In more detail, the project focusses on three areas. The first area is about query access models where algorithms can access data only via asking certain kinds of questions. A main thrust is to completely understand the query complexity of fundamental problems such as submodular function optimization and matroid intersection. The second area is the development of new approximation-algorithm techniques to tackle outlier-detection problems in clustering. The project will also focus on richer objective classes for clustering, thereby paving the way for integer convex optimization. The third area is the development of the primal-dual optimization schema to design faster parallel algorithms, especially for perfect matchings in graphs, which is a fundamental problem in algorithms. By addressing these questions, this project will create new algorithmic paradigms that will be useful for tackling a range of modern-day relevant problems.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.