Submodular Optimization

Follow this topic Ask about this topic

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

52 papers7 papers in the last four weeks, down 12% on the four weeks before. 0.0% of all new papers.

When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?
Oct 18, 2026Qixin Zhang, Shi Fu, Shengminjie Chen +2Greedy Optimization Submodular Optimization
College of Computing and Data Science, Nanyang Technological University, Singapore · Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China · School of Artificial Intelligence, Nanjing University, Nanjing, China
Mobility-Budget-Constrained Submodular Maximization for Distributed Semantic Multi-Robot Exploration
Oct 13, 2026Changxuan Yao, Sandilya Sai Garimella, Lu Gan +1Multi-Robot Exploration Informative Path Planning
The authors are with the Institute of Robotics and Intelligent Machines, Georgia Institute of Technology, Atlanta, GA 30332, USA.
Failure-Resilient Multi-Robot Coordination with $k$ -Connectivity Constrained Submodular Maximization
Oct 9, 2026Yoonjae Hwang, Hojune Kim, Ellen Novoseller +2Resilient Multi-Robot Coordination Multi-Robot Coordination
School of Computer Science, University of Southern California, Los Angeles, CA, USA · U.S. Army DEVCOM Army Laboratory
Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations
Oct 4, 2026Thi Ngoc Anh Vu, Trung Thanh Nguyen, Khaled Elbassioni +1Submodular Optimization Social Choice Theory
Faculty of Computer Science, Phenikaa University, Hanoi 12116, Vietnam · DataOptLab, National Economics University, Hanoi 11616, Vietnam · Khalifa University of Science and Technology, Abu Dhabi 127788, UAE +1
Geometry-Dependent Approximation for Non-Monotone $k$ -Submodular Maximization
Oct 2, 2026Vaneet AggarwalSubmodular Optimization Approximation Algorithms
Purdue University
Redundancy Meets Synergy: Dependency-aware Expert Selection for MoE via Submodular Optimization
Sep 30, 2026Zheng Lin, Shaoke Fang, Yuxin Zhang +6Submodular Optimization Mixture-of-Experts Pruning
Interdisciplinary Centre for Security, Reliability and Trust, University of Luxembourg, Luxembourg · Department of Computer Science, Peking University, China · Institute of Space Internet, Fudan University, China +4
Geometry-Dependent Online and Offline Approximation for Non-Monotone DR-Submodular Maximization
Sep 30, 2026Vaneet Aggarwal, Yiyang LuSubmodular Optimization Regret Minimization
Purdue University
PC-SubMax: Efficient Prompt Compression via Regularized Submodular Maximization
Sep 26, 2026Ziyi Zhang, Shuang Cui, Haotian Zhang +1Prompt Compression Efficient Language Model Inference
Soochow University
Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids
Sep 21, 2026Shi Fu, Youming Qiao, Dacheng Tao +2Submodular Optimization Combinatorial Optimization
College of Computing and Data Science, Nanyang Technological University, Singapore · Centre for Quantum Software and Information, University of Technology Sydney, Australia · School of Computing and Information Technology, Great Bay University, China
Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering
Sep 14, 2026Lars Rohwedder, Rico ZenklusenSubmodular Optimization Markov Decision Processes
University of Southern Denmark, Odense, Denmark · ETH Zurich, Zurich, Switzerland
Truncated Noisy Best-Response Algorithms: Toward Game Theoretic Learning with Safety Guarantees
Sep 10, 2026Vartika Singh, Philip N. BrownSubmodular Optimization Multi-Agent Coordination
Blue Yonder, India · University of Colorado Colorado Springs, CO 80918, USA
A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse
Sep 9, 2026Shi Fu, Qixin Zhang, Dacheng TaoSubmodular Optimization Query Complexity
Nanyang Technological University, Singapore
Dimension Dependent Correlation Gap Bounds under Restricted Independence
Sep 2, 2026Arjun RamachandraSubmodular Optimization
Decision Sciences Area, Indian Institute of Management Bangalore, India.
Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor
Sep 2, 2026Vaneet Aggarwal, Yiyang LuSubmodular Optimization Regret Minimization
Purdue University
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 Optimization Follow-the-Regularized-Leader
Purdue University, West Lafayette, IN, USA · Mila - Quebec AI Institute/McGill University, Montreal, QC, Canada
Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy
Aug 25, 2026Zongqi Wan, Zhijie ZhangSubmodular Optimization Bandit Learning
Great Bay University · Fuzhou University
Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees
Aug 20, 2026Yu Chen, Ruishuo Chen, Xun Wang +2Submodular Optimization LLM Agent Skill Learning
Institute for Interdisciplinary Information Sciences, Tsinghua University
Submodular Policy Learning for Distributed Task Allocation in Open Multi-Agent Systems
Aug 14, 2026Jing Liu, Luca Ballotta, Yangyang Yang +3Multi-Agent Systems Policy Learning
School of Mathematics, East China University of Science and Technology, Shanghai 200237, China · Department of Information Engineering, University of Padova, 35131 Padova, Italy · School of Mathematics and the Key Laboratory of Smart Manufacturing in Energy Chemical Process, Ministry of Education, East China University of Science and Technology, Shanghai 200237, China
Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learning
Aug 12, 2026Vaneet AggarwalSubmodular Optimization Combinatorial Multi-Armed Bandits
V. Aggarwal is with Purdue University, West Lafayette IN, USA
Multitask Pareto Optimization for Monotone Submodular Problems with Dynamic Constraints
Aug 11, 2026Liam Wigney, Frank NeumannSubmodular Optimization Evolutionary Multitask Optimization
Optimisation and Logistics School of Computer Science and Information Technology Adelaide University Adelaide, Australia
Understanding Submodular Information Measure Based Objectives for Representation Learning: A Variance and Separation Perspective
Jul 30, 2026Rishabh Iyer, Truong Pham, Anay MajeeRepresentation Geometry Submodular Optimization
The University of Texas at Dallas, Richardson, TX, USA · Adobe, San Jose, CA, USA
Advancing Optimal Subset Oracle via Learning Relaxation of Neural Set Functions
Jul 13, 2026Yongquan Shi, Zijing Ou, Shiping Wang +1Submodular Optimization Surrogate-Assisted Optimization
Fuzhou University · Imperial College London · National University of Singapore
How Much Does Correctness Cost? Budgeted Placement of Strong Correctors in a Weak Multi-Agent Swarm
Jul 7, 2026Igor ItkinSubmodular Optimization Multi-Agent System Optimization
Independent Researcher, Tel Aviv, Israel
Data-dependent Evaluations for Budgeted Submodular Maximization
Jul 7, 2026Lejian Zhang, Xueyan Tang, Jing TangSubmodular Optimization Approximation Algorithms
College of Computing and Data Science, Nanyang Technological University, Singapore · Data Science and Analytics Thrust, The Hong Kong University of Science and Technology (Guangzhou), China
Coresets Before Score Sets: Evaluation-Unsupervised Prompt Subset Selection for LLM Benchmarks
Jul 2, 2026Jihan Yao, Gantavya Bhatt, Arnav Das +16Submodular Optimization LLM Evaluation
University of Washington, Seattle · 6NVIDIA · 5LMSYS +3
Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations
Jul 1, 2026Bin Du, Chang Liu, Dingqi Zhu +2Submodular Optimization Distributed Optimization
College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China · School of Artificial Intelligence and Automation at the Huazhong University of Science and Technology, Wuhan, China · School of Aeronautics and Astronautics, Purdue University, West Lafayette, IN 47906, USA
Three-Objective Integral R2 Subset Selection: NP-Hardness and Submodular Approximation
Jun 25, 2026Michael T. M. EmmerichSubmodular Optimization Approximation Algorithms
Toward Trustworthy AI: Multi-Target Adversarial Attacks and Robust Defenses for Continuous Data Summarization
Jun 10, 2026Yuefang Lian, Longkun Guo, Zhongrui Zhao +5Submodular Optimization Adversarial Attacks
Nankai University · James Cook University · Western Sydney University +5
Robust Active Learning for Few-Shot Example Selection in Text-to-SQL
Jun 8, 2026Arash PourhabibSubmodular Optimization LLM Grounding
NVIDIA
Avoiding Exponential Blow-Up in Distributive Lattice Submodular Minimization
Jun 8, 2026Ishant ShanuSubmodular Optimization

Oct 18, 2026J/K move · Enter open · S save

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

Qixin Zhang, Shi Fu, Shengminjie Chen, Chao Qian+1

College of Computing and Data Science, Nanyang Technological University, Singapore · Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China · School of Artificial Intelligence, Nanjing University, Nanjing, China

Greedy Optimization Submodular Optimization Approximation Algorithms

Open paper AskPDF arXiv

Weakly submodular maximization finds numerous applications in machine learning, data mining and statistics. In particular, under a cardinality constraint, the standard greedy algorithm is known to attain the tight

(1-e^{-γ})

-approximation guarantee, where

γ

denotes the submodularity ratio. However, when considering general matroid constraints, how well standard greedy can perform has remained a longstanding open question. In this paper, we resolve this question by studying the worst-case approximation guarantee

R_{\mathrm{gr}}(γ,r)

of standard forward greedy, where

r

is the rank of matroid. Specifically, our first contribution is the following refined lower bound \begin{equation*} R_{gr}(γ,r)\ge \max\left{ \fracγ{r}, \frac{γ^2} {B_γ+\sqrt{γ(r-1)}}, \frac{γ^{r+1}} {2-γ+γ^{r+1}}, \frac{γ^2} {14\left(B_γ+\sqrt{γ(1-γ)(r-1)}\right)} \right}, \end{equation*} where

B_γ\triangleq2-γ+γ^2

. This lower bound not only strictly improves upon the previous guarantee of

0.4γ^2/(1+\sqrt{γr})

, but also can recover the classical

1/2

-approximation guarantee at

γ=1

. Subsequently, a corresponding upper bound is established for

R_{\mathrm{gr}}(γ,r)

, namely, \begin{equation}\label{eq_upper_abstract} R_{gr}(γ,r) \le\min\left{\frac{1}{2},20\max\left{\fracγ{r}, \frac{γ^2}{B_γ+ \sqrt{γ(1-γ)(r-1)}}\right}\right}. \end{equation} For every fixed

γ\in(0,1)

, this equation effectively sharpens the recent

O_γ(1/\log(n-1))

upper bound to

O_γ(r^{-1/2})

, where

n

is the size of ground set. Putting all these results together, we eventually can obtain

R_{gr}(γ,r) = Θ\left( \max\left\{\fracγ{r}, \frac{γ^2} {1+\sqrt{γ(1-γ)r}}\right\} \right).