5 papers
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…
Submodular Ground-Set Pruning: Monotone Tightness and a Non-Monotone Separation
Alan Kuhnle
Large-scale subset selection asks for a small useful set of examples, features, sensors, seed users, or context passages from an enormous ground set. Submodular maximization is a c…
Bicriteria Submodular Maximization
Moran Feldman, Alan Kuhnle
Submodular functions and their optimization have found applications in diverse settings ranging from machine learning and data mining to game theory and economics. In this work, we…
ResQue Greedy: Rewiring Sequential Greedy for Improved Submodular Maximization
Joan Vendrell Gallart, Alan Kuhnle, Solmaz Kia
This paper introduces Rewired Sequential Greedy (ResQue Greedy), an enhanced approach for submodular maximization under cardinality constraints. By integrating a novel set curvatur…
Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization
Ankur Nath, Alan Kuhnle
Modern instances of combinatorial optimization problems often exhibit billion-scale ground sets, which have many uninformative or redundant elements. In this work, we develop light…