Yan-Hui Zhu

A Learning-Augmented Framework for Knapsack-Constrained Submodular Maximization Problems

Many machine learning tasks involve maximizing a submodular function with constraints. However, constrained submodular maximization problems are known to be NP-hard. Although there exist efficient approximation algorithms, approximation guarantees cannot be improved without auxiliary information, unless P = NP. In this...