7 papers
Submodular Welfare under Routing Coupling: A Hierarchical Decomposition with Perturbation Guarantees
Joan Vendrell Gallart, Nhat-Minh Tang-Nguyen, Alan Kuhnle +1
This paper studies joint submodular welfare maximization and routing over graphs, where agents select items under diminishing returns and transport them through a network with cong…
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…
A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization
Ankur Nath, Alan Kuhnle
Recently, there has been much work on the design of general heuristics for graph-based, combinatorial optimization problems via the incorporation of Graph Neural Networks (GNNs) to…