Junior Faculty Fellow Alina Ene Receives NSF CAREER Award

Assistant Professor of Computer Science and Hariri Junior Faculty Fellow Alina Ene has received the National Science Foundation’s prestigious CAREER Award. NSF CAREER Awards are given in support of early-career faculty who have the potential to serve as academic role models in research and education and to lead advances in the mission of their department or organization.

Ene received the award for her proposal, “New Algorithms for Submodular Optimization.” The research will develop scalable algorithmic approaches with improved empirical performance for submodular optimization and to transfer theoretical insights to applications. Though submodular optimization is well-suited for a variety uses, most existing algorithms cannot be effectively applied to modern datasets – her work aims to change that.

Full Abstract: Submodular optimization provides general solutions to a wide range of applications from monitoring water distribution networks to summarizing large corpora of documents and speech recognition. Most of the existing submodular optimization algorithms are not suitable for modern datasets, since they are designed for worst-case instances and they suffer from prohibitive running times and poor empirical performance. This project aims to develop scalable algorithmic approaches with improved empirical performance for submodular optimization and to transfer theoretical insights to applications. The proposed research brings together insights from computer science, mathematics and optimization, and strengthens connections among these fields. The project will involve training the next wave of students and equipping them with technical tools to work in all these fields.

The project focuses on three inter-related research directions in submodular function optimization:
(a) Design faster algorithms for minimizing submodular functions with a decomposable or sum structure. The approach is to build on a rich set of tools from both discrete and continuous optimization.
(b) Design algorithms for constrained submodular maximization problems with improved approximation guarantees and faster running times. The focus is on settling the approximability of constrained submodular maximization problems with a non-monotone objective and on designing faster algorithms for central families of constraints.
(c) Design algorithms and frameworks for allocation or labeling problems with submodular costs. The main goal is to obtain more expressive algorithmic frameworks and efficient algorithms.