Overview

Submodular optimization uses diminishing returns to model problems such as coverage, data selection, and allocating tasks or resources. Because exact optimization is often computationally hard, common methods include greedy selection, continuous relaxations with rounding, and local exchanges, with guarantees for constraints such as cardinality, knapsack, and matroids. Current work also studies non-monotone objectives and applications in language-model data selection, robotics, and benchmark design. A central tension is preserving strong approximation or regret guarantees while handling limited feedback, communication, changing constraints, and more general objectives.

Latest papers

CardsList

61 papers7 papers in the last four weeks, down 22% on the four weeks before. 0.1% of all new papers.

  1. Bandit Online Submodular Minimisation Using Zeroth-Order Oracles

    Nov 17, 2026Amir Ali Farzin, Philipp Braun, Iman ShamesOnline Submodular OptimizationSubmodular Optimization

  2. DeFSM: Robust and Efficient Decentralization of Federated Submodular Maximization

    Nov 9, 2026Duc A. Tran, Dung Truong, Duy LeFederated Learning AggregationSubmodular Optimization

  3. Consistent Submodular Maximization with Full Foresight

    Nov 4, 2026Eric Balkanski, Paul Dütting, Federico Fusco +4Online Submodular OptimizationSubmodular Optimization

  4. Cooperative Multi-Agent Reinforcement Learning with Submodular Trajectory Rewards

    Nov 3, 2026Yasaman Zolfimoselo, Nikolas Geroliminis, Maryam KamgarpourCooperative MARLReinforcement Learning

  5. Query-based Submodular Data Selection for Efficient Instruction Tuning

    Nov 2, 2026Zhenghao Zhao, Yasutomo Kawanishi, Huihuo Zheng +2Data SelectionInstruction-Tuning Data Selection

  6. When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?

    Oct 18, 2026Qixin Zhang, Shi Fu, Shengminjie Chen +2Greedy OptimizationSubmodular Optimization

  7. Mobility-Budget-Constrained Submodular Maximization for Distributed Semantic Multi-Robot Exploration

    Oct 13, 2026Changxuan Yao, Sandilya Sai Garimella, Lu Gan +1Multi-Robot ExplorationInformative Path Planning

  8. Failure-Resilient Multi-Robot Coordination with kk-Connectivity Constrained Submodular Maximization

    Oct 9, 2026Yoonjae Hwang, Hojune Kim, Ellen Novoseller +2Resilient Multi-Robot CoordinationMulti-Robot Coordination

  9. Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations

    Oct 4, 2026Thi Ngoc Anh Vu, Trung Thanh Nguyen, Khaled Elbassioni +1Submodular OptimizationSocial Choice Theory

  10. Redundancy Meets Synergy: Dependency-aware Expert Selection for MoE via Submodular Optimization

    Sep 30, 2026Zheng Lin, Shaoke Fang, Yuxin Zhang +6Submodular OptimizationMixture-of-Experts Pruning

  11. Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids

    Sep 21, 2026Shi Fu, Youming Qiao, Dacheng Tao +2Submodular OptimizationCombinatorial Optimization

  12. Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering

    Sep 14, 2026Lars Rohwedder, Rico ZenklusenSubmodular OptimizationMarkov Decision Processes

  13. Truncated Noisy Best-Response Algorithms: Toward Game Theoretic Learning with Safety Guarantees

    Sep 10, 2026Vartika Singh, Philip N. BrownSubmodular OptimizationMulti-Agent Coordination

  14. Dimension Dependent Correlation Gap Bounds under Restricted Independence

    Sep 2, 2026Arjun RamachandraSubmodular Optimization

  15. Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization

    Aug 31, 2026Yiyang Lu, Mohammad Pedramfar, Vaneet AggarwalSubmodular OptimizationFollow-the-Regularized-Leader

  16. Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees

    Aug 20, 2026Yu Chen, Ruishuo Chen, Xun Wang +2Submodular OptimizationLLM Agent Skill Learning

  17. Submodular Policy Learning for Distributed Task Allocation in Open Multi-Agent Systems

    Aug 14, 2026Jing Liu, Luca Ballotta, Yangyang Yang +3Multi-Agent SystemsPolicy Learning

  18. Multitask Pareto Optimization for Monotone Submodular Problems with Dynamic Constraints

    Aug 11, 2026Liam Wigney, Frank NeumannSubmodular OptimizationEvolutionary Multitask Optimization

  19. Understanding Submodular Information Measure Based Objectives for Representation Learning: A Variance and Separation Perspective

    Jul 30, 2026Rishabh Iyer, Truong Pham, Anay MajeeRepresentation GeometrySubmodular Optimization

  20. Advancing Optimal Subset Oracle via Learning Relaxation of Neural Set Functions

    Jul 13, 2026Yongquan Shi, Zijing Ou, Shiping Wang +1Submodular OptimizationSurrogate-Assisted Optimization