XTRIPODS: Machine Learning Augmented Algorithms with Weak and Sparse Predictions

Machine learning (ML) augmented algorithms have emerged as a powerful framework that incorporates machine-learned predictions into algorithm design. This framework has demonstrated that traditional algorithms can be significantly enhanced using machine learning while retaining some worst-case performance guarantees. This project aims to study ML-augmented algorithms that only have access to weak and sparse predictions. Such scenarios can arise when obtaining abundant and accurate data for training is challenging, or when running heavy predictors that can otherwise incur a non-trivial overhead in time-critical or resource-constrained systems. By understanding the power and limitations of using weak and sparse predictions, the project seeks to make ML augmented algorithms more applicable. Additionally, the project will prepare the students to tackle challenges in this rapidly expanding field, particularly by reaching out to and supporting community college students in their educational journey toward four-year colleges and beyond. This project also aims to further unlock the potential of machine learning-augmented algorithms by exploring their capabilities when operating on sparse or weak predictions. Sparse predictions, which may occur when training data is limited, arise when the machine learning model produces few predictions for certain inputs. Weak predictions arise, for example, when predictions are given as ranges of values rather than specific values. Both scenarios pose unique challenges for algorithm design. This project will investigate the design considerations for machine learning-augmented algorithms in these contexts, seeking to understand the tradeoff between prediction quality and resulting performance guarantees, ultimately advancing the understanding and applicability of machine learning-augmented algorithms in real-world scenarios. 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.