2 papers
cs.LG2026
Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions
Yixin Chen, Alan Kuhnle
Submodular functions -- functions exhibiting diminishing returns -- are central to machine learning. When the objective is monotone and non-negative, the greedy algorithm achieves…
cs.DS2025
Discretely Beyond : Guided Combinatorial Algorithms for Submodular Maximization
Yixin Chen, Ankur Nath, Chunli Peng +1
For constrained, not necessarily monotone submodular maximization, all known approximation algorithms with ratio greater than require continuous ideas, such as queries to the…