Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Non-monotone Submodular Optimization: $p$-Matchoid Constraints and Fully Dynamic Setting
Authors: Kiarash Banihashem, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present the main result of this paper in the following theorem. Theorem 1.1 (Main Theorem). Let 0 < ̈ 1 be a parameter. Let M(V, I) be a p-matchoid consisting of m matroids M1(V1, I1), M2(V2, I2), . . . , Mm(Vm, Im), and let k denote the size of the largest independent set in I. Let f : 2V R 0 be a (not necessarily monotone) submodular function defined over subsets of the ground set V. Then, there exists a dynamic algorithm for maximizing the function f subject to the p-matchoid constraint M(V, I), which maintains a (2p+2 p p(p + 1)+1+)-approximate solution at any time t during the sequence of updates, while performing an expected amortized O(̈ 3pk4 log2 k) oracle queries per update. As a byproduct, we obtain another result for the special case of cardinality k, as stated below. Corollary 1.2. There exists a dynamic algorithm for non-monotone submodular maximization subject to a matroid constraint of rank k (including the cardinality constraint k), which achieves a (5.82 + ̈)-approximate solution using O(̈ 3k4 log2 k) oracle queries per update. Our algorithm for the cardinality case is an improvement upon the approximation of the dynamic algorithm presented by Banihashem et al.Banihashem et al. [2023], which maintains a (8 + ̈)-approximate solution with an expected amortized O(̈ 2k2 log3(k)) oracle queries per update. Under the assumption that the submodular function f is monotone, the approximation guarantee of Theorem 1.1 can be strengthened. An adaptation of our algorithm then yields the following side result: Proposition 1.3. There exists a dynamic algorithm for monotone submodular maximization subject to a p-matchoid constraint of rank k with (4p + ̈) approximation guarantee and O(̈ 3pk4 log2(k)) update time. |
| Researcher Affiliation | Academia | Kiarash Banihashem University of Maryland College Park, MD, USA EMAIL Samira Goudarzi University of Maryland College Park, MD, USA EMAIL Mohammad Taghi Hajiaghayi University of Maryland College Park, MD, USA EMAIL Peyman Jabbarzade University of Maryland College Park, MD, USA EMAIL Morteza Monemizadeh TU Eindhoven Eindhoven, The Netherlands EMAIL |
| Pseudocode | Yes | Algorithm 1 Matchoid Construction Procedure Init(V): 1: A0 , and B0 Rate Sampling(V) 2: Return Recursion(A0, B0) Procedure Rate Sampling(V): 1: Sample each element e V i.i.d with probability q = (p + p p2 + p + 1) 1 2: Return sampled set B0 in Step 1 Procedure Recursion(Ai 1, Bi 1): 1: Bi Filtering(Ai 1, Bi 1) 2: if |Bi| > 0 then 3: Sample an element ei Bi uniformly at random 4: Ai Extension(Ai 1, ei) 5: Return Recursion(Ai, Bi) 6: Let i i 1 7: Return Ai Procedure Filtering(Ai 1, Bi 1): 1: Bi 2: for every element e Bi 1 do 3: Ui(e) Find Swaps(Ai 1, e) 4: store Ui(e) for element e as it may be used later in Procedure Extension 5: if Ui(e) , Fail then 6: Bi Bi e 7: Return Bi Procedure Extension(Ai 1, ei): 1: Set weight w(ei) (ei|Ai 1) 2: Ai Ai 1 Ui(ei) + ei 3: Return Ai Procedure Find Swaps(Ai 1, e): 1: Ui(e) Dependency Detection(Ai 1, e) 3: ̈ max n (1 + c) w(Ui(e)), ̈MAX 4: if (e|Ai 1) ̈ then 5: Return Ui(e) 6: else 7: Return Fail Procedure Dependency Detection(Ai 1, e): 1: Ui(e) 2: for j = 1 to m do 3: if (Ai 1 + e) V j < Ij then 4: Xj {e Ai 1|(Ai 1 e +e) Vj Ij} 5: x j arg mine Xj w(e ) 6: Ui(e) Ui(e) + xj 7: Return Ui(e) Algorithm 2 Update Operations Procedure Insert(e): 1: With probability 1 q Ignore e and return 2: B0 B0 + e 3: for i 1 to i do 4: Ui(e) Find Swaps(Ai 1, e) 5: if Ui(e) = FAIL then 6: Return 7: Bi Bi + e 8: With probability ri = 1 |Bi|: ① ei e ② Ai Extension(Ai 1, ei) ③ Return Recursion(Ai, Bi) Procedure Delete(e): 1: for i 0 to i do 2: if e < Bi then 3: Return 4: Bi Bi e 5: if ei = e then 6: if |Bi| > 0 then 7: Sample an element ei Bi uniformly at random 8: Ai Extension(Ai 1, ei) 9: Return Recursion(Ai, Bi) 10: Let i i 1 11: Return Ai |
| Open Source Code | No | The paper is theoretical and presents algorithms and proofs. It does not mention any open-source code release, repository links, or code in supplementary materials. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and approximation guarantees for submodular maximization under p-matchoid constraints. It does not use or refer to any specific datasets, public or otherwise. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental evaluation on datasets, thus there is no mention of dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not include experimental results. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and proofs. It does not describe any experimental setup or software implementation details, thus no specific software dependencies or versions are mentioned. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup, hyperparameters, or training configurations. Its focus is on algorithm design and theoretical approximation guarantees. |