CAREER: Modern Aspects of Learning-Augmented Algorithms

Many important artificial intelligence computing systems rely on algorithms to make decisions about scheduling, routing, and the use of limited resources. Traditional algorithms are dependable because their performance can be guaranteed in all cases, but they often cannot take advantage of recurring patterns in data that could make them faster or more effective. By contrast, machine learning methods can detect useful patterns, but their guidance may become unreliable when conditions change or when the learned estimates are inaccurate. This project develops new algorithmic methods that combine the reliability of traditional algorithms with the adaptability of machine learning. The resulting advances can improve the efficiency and robustness of computing systems that support modern infrastructure, while also helping train students in an emerging area at the intersection of algorithms and data-driven decision-making. This project studies learning-augmented algorithms, also known as algorithms with predictions, which use machine-learned forecasts to improve performance while retaining provable worst-case guarantees. The research will investigate several directions: determining how to achieve strong improvements using fewer or weaker predictions; designing prediction frameworks that apply across broad classes of algorithmic problems; and extending the learning-augmented framework to problems that have previously been studied through other beyond-worst-case approaches. These efforts will establish new performance guarantees, clarify when prediction-guided methods are effective, and deepen understanding of the benefits and limitations of combining machine learning with rigorous algorithm design. 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. NSF Award ID: 2542925 | Program: 01002930DB NSF RESEARCH & RELATED ACTIVIT,01003031DB NSF RESEARCH & RELATED ACTIVIT,01002627DB NSF RESEARCH & RELATED ACTIVIT | Principal Investigator: Ali Vakilian | Institution: Virginia Polytechnic Institute and State University, BLACKSBURG, VA | Award Amount: $419,700 View on NSF Award Search: https://www.nsf.gov/awardsearch/show-award/?AWD_ID=2542925 View on Research.gov: https://www.research.gov/awardapi-service/v1/awards/2542925.html