Submodular Optimization

Ask about this topic

Momentum

7 papers in the last four weeks, up 17% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28
View on map

Latest papers 35

All topics
CardsList

  1. 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

    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

  2. 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

    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

  3. Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization

    Sep 30, 2026Vaneet AggarwalSubmodular OptimizationRegret Minimization

    Purdue University

  4. 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

    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

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

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

    University of Southern Denmark, Odense, Denmark · ETH Zurich, Zurich, Switzerland

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

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

    Blue Yonder, India · University of Colorado Colorado Springs, CO 80918, USA

  7. A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over 2−22-\sqrt{2} Entails Exponential Queries or Linear Recourse

    Sep 9, 2026Shi Fu, Qixin Zhang, Dacheng TaoSubmodular OptimizationQuery Complexity

    Nanyang Technological University, Singapore

  8. Dimension Dependent Correlation Gap Bounds under Restricted Independence

    Sep 2, 2026Arjun RamachandraSubmodular Optimization

    Decision Sciences Area, Indian Institute of Management Bangalore, India.

  9. Online Non-Monotone DR-Submodular Maximization Matching the Offline 0.4010.401 Factor

    Sep 2, 2026Vaneet Aggarwal, Yiyang LuSubmodular OptimizationRegret Minimization

    Purdue University

  10. 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

    Purdue University, West Lafayette, IN, USA · Mila - Quebec AI Institute/McGill University, Montreal, QC, Canada

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

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

    Institute for Interdisciplinary Information Sciences, Tsinghua University

  12. Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning

    Aug 12, 2026Vaneet AggarwalSubmodular OptimizationCombinatorial Multi-Armed Bandits

    V. Aggarwal is with Purdue University, West Lafayette IN, USA

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

    Aug 11, 2026Liam Wigney, Frank NeumannSubmodular OptimizationMulti-Objective Evolutionary Optimization

    Optimisation and Logistics School of Computer Science and Information Technology Adelaide University Adelaide, Australia

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

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

    The University of Texas at Dallas, Richardson, TX, USA · Adobe, San Jose, CA, USA

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

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

    Fuzhou University · Imperial College London · National University of Singapore

  16. How Much Does Correctness Cost? Budgeted Placement of Strong Correctors in a Weak Multi-Agent Swarm

    Jul 7, 2026Igor ItkinSubmodular OptimizationMulti-Agent System Optimization

    Independent Researcher, Tel Aviv, Israel

  17. Data-dependent Evaluations for Budgeted Submodular Maximization

    Jul 7, 2026Lejian Zhang, Xueyan Tang, Jing TangSubmodular OptimizationApproximation 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

  18. Coresets Before Score Sets: Evaluation-Unsupervised Prompt Subset Selection for LLM Benchmarks

    Jul 2, 2026Jihan Yao, Gantavya Bhatt, Arnav Das +16Submodular OptimizationLLM Evaluation

    University of Washington, Seattle · 6NVIDIA · 5LMSYS +3

  19. Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations

    Jul 1, 2026Bin Du, Chang Liu, Dingqi Zhu +2Submodular OptimizationDistributed 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

  20. Three-Objective Integral R2 Subset Selection: NP-Hardness and Submodular Approximation

    Jun 25, 2026Michael T. M. EmmerichSubmodular OptimizationApproximation Algorithms

  21. Toward Trustworthy AI: Multi-Target Adversarial Attacks and Robust Defenses for Continuous Data Summarization

    Jun 10, 2026Yuefang Lian, Longkun Guo, Zhongrui Zhao +5Submodular OptimizationAdversarial Attacks

    Nankai University · James Cook University · Western Sydney University +5

  22. Robust Active Learning for Few-Shot Example Selection in Text-to-SQL

    Jun 8, 2026Arash PourhabibSubmodular OptimizationLLM Grounding

    NVIDIA

  23. Avoiding Exponential Blow-Up in Distributive Lattice Submodular Minimization

    Jun 8, 2026Ishant ShanuSubmodular Optimization

  24. Thresholded Local Hyper-Flow Diffusion

    Jun 8, 2026Meher Chaitanya, Sebastian Dalleiger, Luana RuizSubmodular OptimizationGraph Clustering

    KTH Royal Institute of Technology · Stockholm, Sweden 114 28 · Johns Hopkins University +1

  25. Minibatch Selection for Language Models via Partition Matroid Constrained Gradient Matching

    Jun 6, 2026Prayas Agrawal, Prateek Chanda, Ishita Khatri +3Submodular OptimizationLLM Fine-Tuning

    Department of Computer Science and Engineering, Indian Institute of Technology Bombay · Microsoft Research India · Centre for Machine Intelligence and Data Science, Indian Institute of Technology Bombay +1

  26. A General Framework for Dynamic Consistent Submodular Maximization

    Jun 3, 2026Paul Dütting, Federico Fusco, Silvio Lattanzi +3Submodular OptimizationApproximation Algorithms

    1Google Research · 2Dept. of Computer, Control and Management Engineering, Sapienza University of Rome · 3EPFL

  27. How Much Is a Dataset Worth? Scaling Laws, the Vendi Score, and Matrix Spectral Functions

    May 28, 2026Jeff A. Bilmes, Gantavya Bhatt, Arnav M. DasSubmodular OptimizationNeural Scaling Laws

    Department of Electrical & Computer Engineering 2Paul G. Allen School of Computer Science & Engineering University of Washington, Seattle Seattle, WA 98195

  28. Complement Submodular Information Measures for Balanced and Robust Data Selection

    May 23, 2026Rishabh IyerSubmodular OptimizationData Selection

    Department of Computer Science The University of Texas at Dallas Richardson, TX 75080

  29. Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions

    May 8, 2026Yixin Chen, Alan KuhnleSubmodular OptimizationApproximation Algorithms

    Department of Computer Science & Engineering, Texas A&M University

  30. Accelerated Relax-and-Round for Concave Coverage Problems

    May 7, 2026Matthew Fahrbach, Mehraneh Liaee, Morteza ZadimoghaddamSubmodular OptimizationApproximation Algorithms

    Google Research