betaFeedback

WorksComputer Science

From Linear to Polylogarithmic: Dynamic Submodular Maximization over Matroids

Abstract

We study the problem of submodular maximization under a matroid constraint. In this problem, there is a monotone submodular function f:2N→R+f: 2^{N} \rightarrow \mathbb{R}^+ and a matroid M(N,I)M(N, I), accessible via value and independence oracles and the goal is to find the independent set S∈IS \in I maximizing the objective function, i.e., f(S)=max⁡I∈If(I)f(S) = \max_{I \in I} f(I). In the fully dynamic setting, the active ground set N⊆NN \subseteq N evolves through element insertions and deletions. The goal is to maintain a solution S⊆NS \subseteq N with S∈IS \in I and f(S)=max⁡I⊆N,,I∈If(I)f(S) = \max_{I \subseteq N,, I \in I} f(I) after each update. Two approximation algorithms have been proposed to solve this problem: Dütting et al. developed a (4+ε)(4+ε)-approximation algorithm with an expected amortized update time of O ⁣(k2εlog⁡klog⁡nlog⁡3kε)O\!\bigl(\frac{k^2}ε \log k \log n \log^3 \frac{k}ε\bigr), and Banihashem et al. achieved a similar approximation with a better update time O ⁣(klog⁡klog⁡3kε)O\!\bigl(k \log k \log^3 \frac{k}ε\bigr). However, these methods both become inefficient when the rank kk of the matroid is large (e.g., when k=no(1)k = n^{o(1)}). The central open question in this line of work is whether a fully dynamic algorithm with polylogarithmic update time exists. We resolve this question by presenting the first fully dynamic algorithm for submodular maximization over matroids with polylogarithmic update time. Our algorithm maintains a (4+ε)(4+ε)-approximate solution with expected amortized update time poly(log⁡n,ε−1)poly(\log n, ε^{-1}), where n=∣N∣n = |N|. In particular, the update time is independent of the matroid rank kk, thereby eliminating the dependence on kk and settling the open problem.

Introduction

Many Web applications repeatedly need to select a high-quality subset of items from a large and continuously changing collection. For example, a Web platform may need to select a set of articles, products, advertisements, or recommended items to display to users. The quality of a selected set is often naturally modeled by a submodular function: adding an item provides diminishing marginal benefit as increasingly similar or redundant items are already selected. Submodular objectives have been widely used to model coverage and information-gathering objectives [6], as well as diversity in recommendation and search [5, 1].

In practice, however, a platform cannot select an arbitrary subset of items. The selected items must satisfy combinatorial constraints reflecting limited display space, business rules, or diversity requirements. Matroid constraints provide a particularly natural and expressive way to model such requirements. For example, a partition matroid can impose quotas on different categories or content providers, such as allowing at most rir_i items from category ii. The rank of the matroid then has a direct interpretation as the total number of available selection slots. More general matroids can capture overlapping eligibility and resource constraints while allowing the algorithm to exchange selected items in a structured way. Thus, submodular maximization under a matroid constraint provides a general framework for balancing the quality of a selection with diversity and resource limitations that arise naturally in Web applications.

The role of the matroid rank is particularly intuitive in recommendation and content-selection systems. Suppose a platform must display at most kk items. A uniform matroid of rank kk models the basic capacity constraint that at most kk items can be selected. A partition matroid can further distribute these kk slots across categories or providers, for example by requiring that no category contribute more than a specified number of items. The submodular objective can then favor selections that cover diverse topics, users, or interests. In this setting, the rank represents the scale of the selection that the platform can maintain, while the matroid structure specifies how those limited slots may be allocated. More sophisticated matroids can similarly represent multiple interacting resource or eligibility constraints.

A defining characteristic of many Web applications is that their underlying collections and interactions evolve continuously. For example, in recommender systems, new items are introduced and users continuously interact with existing items, changing the interaction graph and the information available for recommendation [2, 3]. Real-world recommendation systems must also adapt to changing item-popularity trends while scaling to millions of items [4]. These changes can affect both the objective value of a selected set and its feasibility under application-specific constraints. Recomputing an approximately optimal solution from scratch after every insertion or deletion can be prohibitively expensive at Web scale. This motivates the fully dynamic version of submodular maximization, in which the active ground set changes over time and the algorithm must efficiently maintain a near-optimal feasible solution after each update.

For instance, consider a recommendation platform that maintains a set of items to display while promoting diversity across categories or providers [1]. The utility of a recommendation set can be modeled by a submodular function that captures user engagement, coverage, or diversity, while category or provider quotas can be represented by a matroid constraint. As new items become available and existing items are removed, the platform must continuously update its recommendations to adapt to the changing collection [3, 2]. Ideally, these updates should be processed in time that is polylogarithmic in the size of the system, rather than in time that grows with the number of available items or with the matroid rank.

Our work addresses this challenge by developing a fully dynamic algorithm for monotone submodular maximization under a matroid constraint with expected amortized update time poly(log⁡n,ϵ−1)\mathrm{poly}(\log n,\epsilon^{-1}), independent of the matroid rank. This result provides a general algorithmic framework for maintaining approximately optimal constrained selections in dynamic Web environments, where both the collection of available items and the feasible solution may change continuously.

Submodular functions naturally express the principle of diminishing returns: the gain from adding an element decreases as the chosen set grows. Formally, a set function f:2N→R+f: 2^{\mathcal{N}} \rightarrow \mathbb{R}^+ defined on a finite ground set N\mathcal{N} is submodular if, for every A⊆B⊆NA \subseteq B \subseteq \mathcal{N} and element e∈N∖Be \in \mathcal{N} \setminus B, f(A∪{e})−f(A)≥f(B∪{e})−f(B)f(A \cup \{e\}) - f(A) \geq f(B \cup \{e\}) - f(B). If, in addition, f(A)≤f(B)f(A) \le f(B) for all A⊆BA \subseteq B, then ff is monotone.

Constraints often reflect structural or resource limitations—such as selecting a subset of features, sensors, or network links, which can be modeled as a matroid to capture independence and exchange properties. A matroid M=(N,I)\mathcal{M} = (\mathcal{N}, \mathcal{I}) is defined by a collection of independent sets I⊆2N\mathcal{I} \subseteq 2^{\mathcal{N}} that satisfy non-emptiness, heredity, and the exchange property. The rank kk of M\mathcal{M} is the size of its largest independent set. The classical offline problem of submodular maximization under a matroid constraint seeks an independent set S∈IS \in \mathcal{I} that maximizes f(S)f(S), i.e., max⁡S∈If(S)\max_{S \in \mathcal{I}} f(S).

Submodular maximization has a broad range of applications. In machine learning, it appears in feature selection [23, 42], data summarization [8, 15], and active learning [12, 13]. In data mining and network science, it models influence maximization [7, 14] and community detection [27, 24], while in network design [25, 26], it captures objectives related to connectivity, reliability, and information flow.

The dynamic variant of submodular maximization under a matroid constraint has received growing attention [16, 17, 9, 41]. Here, the ground set N\mathcal{N} evolves over time through insertions and deletions, and the goal is to maintain an independent set S∈IS \in \mathcal{I} that remains near-optimal for the current instance, while limiting the computational overhead per update. Formally, the algorithm interacts with ff through a value oracle and with M\mathcal{M} through an independence oracle, and must update its maintained solution as the input changes.

While the offline version of submodular maximization under a matroid constraint is well understood—for instance, the classic greedy algorithm attains a (1−1/e)(1 - 1/e)-approximation [36]—these offline methods recompute the entire solution from scratch following each change, resulting in linear update time in ∣N∣|\mathcal{N}|. Such costs become prohibitive in large-scale settings, which has spurred interest in efficient dynamic submodular maximization algorithms that offer near-optimal guarantees while maintaining polylogarithmic update times.

Designing efficient algorithms for maintaining near-optimal solutions to monotone submodular maximization under matroid constraints in a fully dynamic setting has been a longstanding challenge (was posed in [34, 17], and remains a natural open problem following [38, 16]). The goal is to handle insertions and deletions of elements while simultaneously achieving two key objectives:

  • maintain a constant-factor approximation (e.g., (4+ϵ)(4+\epsilon)) to the optimal solution, and

  • ensure that each update requires only polylogarithmic time in the size of the ground set, measured in oracle queries to ff and M\mathcal{M}.

Prior work has made substantial progress toward this goal. Dütting et al. [17] provided a (4+ϵ)(4+\epsilon)-approximation algorithm with expected amortized update time O(k2ϵlog⁡klog⁡nlog⁡3kϵ)O\bigl(\frac{k^2}{\epsilon} \log k \log n \log^3 \frac{k}{\epsilon}\bigr). In concurrent and independent work, Banihashem et al. [16] improved this to a linear dependence on kk, achieving O(klog⁡klog⁡3kϵ)O\bigl(k \log k \log^3 \frac{k}{\epsilon}\bigr) expected amortized update time while preserving the same approximation guarantee. Despite these advances, both approaches become computationally expensive when the matroid rank is large, since the update time still grows polynomially with kk.

In this work, we overcome this barrier by introducing the first fully dynamic algorithm for submodular maximization under a general matroid constraint whose update time is polylogarithmic in nn. Our algorithm maintains a (4+ϵ)(4+\epsilon)-approximate solution with expected amortized update time poly(log⁡n,ϵ−1)\mathrm{poly}(\log n, \epsilon^{-1}), independent of the matroid rank kk. This breakthrough ensures that even rapidly evolving datasets can be handled efficiently, resolving the open problem posed by earlier studies.

Overview of Our Algorithm.

Our dynamic algorithm for submodular maximization under matroid constraints builds on the dynamic framework developed for the simpler setting of cardinality constraints [32], which was later extended to submodular cover [37] and submodular matching [11]. Prior to our work, it remained unclear whether these ideas could yield an algorithm with polylogarithmic update time under matroid constraints, whose rich combinatorial structure is notoriously difficult to handle1.

To process elements, the algorithm organizes them into TT hierarchical layers, with TT polylogarithmic in expectation. At each layer ℓ\ell, our data structure maintains an independent set Iℓ∈II_\ell \in \mathcal{I}, together with an auxiliary set I∪ℓ{I^{\cup}}_\ell as the union of all elements present in the independent set II of its preceding levels. A key design choice is that marginal gains are always evaluated with respect to I∪{I^{\cup}} rather than II. Since I∪{I^{\cup}} only grows over time, marginal values are non-increasing, and elements that were discarded at some layer because of their small marginal contribution do not need to be reconsidered. This prevents costly re-evaluations.

Each layer ℓ\ell contains a set of elements EℓE_\ell whose marginal gains with respect to I∪{I^{\cup}} exceed a threshold and are feasible for addition to II under the matroid constraint. These elements are further partitioned into logarithmically many buckets according to their marginal values, and in each layer, the largest bucket is selected for processing. This bucket has two key properties: its elements have nearly equal marginal gains, and processing a constant fraction of them both ensures a substantial contribution to the solution and provides robustness against small deletions. These properties are crucial for controlling solution quality and for bounding the approximation guarantee.

Within each chosen bucket, we employ a sampling mechanism to estimate how many elements should be drawn so that a sufficient number can be successfully added to II without violating independence or, if necessary, by displacing existing elements that are less valuable. Once the sample size is determined, a set SℓS_\ell of that size is drawn uniformly from the bucket. With high probability, most of these elements are successfully added to II. In the case of conflicts, elements currently in II are removed to restore independence while remaining in I∪{I^{\cup}}, and the total marginal gain of the inserted elements is always at least twice that of the evicted ones. This geometric dominance guarantees that the overall loss is bounded and that the approximation ratio is preserved over time.

Insertions and deletions are handled using buffered updates. For insertions, each layer maintains a buffer AℓA_\ell of new elements, and the layer is rebuilt only when the buffer reaches an ϵ\epsilon-fraction of the size of EℓE_\ell. For deletions, a single shared buffer DD is used across all layers, and a layer is rebuilt once an ϵ\epsilon-fraction of its elements have been deleted. These lazy updates spread the cost of reconstruction evenly over time, leading to low amortized query complexity.

Finally, to accommodate elements of widely varying submodular values, we run parallel copies of the algorithm with thresholds of the form τ=ϵ4k⋅2i\tau = \frac{\epsilon}{4k} \cdot 2^i, where ii ranges over integers. Each element participates only in the runs whose thresholds match its value interval, ensuring efficiency across the full value range. This thresholding technique is inspired by the parallel-run method of [34].

Theorem 1. For any ϵ>0\epsilon > 0, there exists a fully dynamic randomized algorithm for submodular maximization under a matroid constraint that maintains an expected (4+ϵ)(4+\epsilon)-approximate solution against an oblivious adversary. The expected amortized update time is poly⁡(log⁡n,1ϵ)\operatorname{poly}(\log n, \frac{1}{\epsilon}), where n=∣N∣n = |\mathcal{N}| is the ground set size.

Next, we highlight the key novelties of our work in comparison with prior dynamic algorithms for submodular maximization under matroid and cardinality constraints. The dynamic algorithm for matroid constraints proposed in [16] achieves an update time linear in the rank kk of the underlying matroid. In contrast, the dynamic algorithm for the cardinality constraint introduced in [32] achieves a polylogarithmic update time. However, neither of these techniques alone can be extended to develop a dynamic algorithm for matroid constraints that maintains a (4+ϵ)(4+\epsilon)-approximate solution with an expected amortized update time of poly(log⁡n,ϵ−1)\mathrm{poly}(\log n, \epsilon^{-1}).

The approach in [16] maintains O(k)O(k) layers and, upon the deletion of an element ee from the current solution, reconstructs the layer ℓ\ell where ee was added, along with all subsequent layers. As a result, this framework cannot be directly transformed into a data structure that supports poly(log⁡n,ϵ−1)\mathrm{poly}(\log n, \epsilon^{-1}) update time under matroid constraints. To overcome this limitation, we partition the active set EℓE_{\ell} in each layer ℓ\ell into logarithmically many buckets according to the marginal values of their elements, and we select the largest bucket for processing. This bucket contains at least O(ϵlog⁡n∣Eℓ∣)O(\frac{\epsilon}{\log n}|E_{\ell}|) elements whose marginal gains are nearly identical. Using a sampling mechanism, we estimate the fraction of elements in this bucket that can be added to the current solution through a single uniform sample. The key insight is that, since all elements added to the solution at layer ℓ\ell have nearly equal marginal gains, as long as only an O(ϵ)O(\epsilon) fraction of them are modified, the maintained solution continues to provide a (4+ϵ)(4+\epsilon)-approximation guarantee. Consequently, unlike the approach in [16], which can tolerate only one update to the maintained solution (and therefore requires O(k)O(k) layers), our method can tolerate changes to an O(ϵ)O(\epsilon) fraction of elements with nearly equal marginal gains. This property enables us to achieve an expected amortized update time of poly(log⁡n,ϵ−1)\mathrm{poly}(\log n, \epsilon^{-1}).

Moreover, while submodular maximization under cardinality or matching constraints is closely related to the matroid-constrained problem—specifically where the matroid is uniform of rank k—extending dynamic algorithms (e.g., [34, 32, 11]) to general matroids is far from trivial. The primary challenge lies in the structural nature of matroids, particularly the strong exchange property, which governs how independence is maintained as elements are inserted or deleted. Under a cardinality constraint, feasibility is a simple function of the set’s size. This simplicity facilitates efficient update operations and enables the maintenance of approximate solutions with amortized polylogarithmic complexity. Similarly, matching constraints possess a specific localized structure that limits the ripple effect of updates. In contrast, for general matroids, maintaining independence requires intricate coordination across the entire ground set; adding or removing a single element can shift the feasibility status of numerous other subsets. Consequently, existing algorithms cannot be directly adapted to general matroids without substantial new insights. Our analysis introduces non-trivial arguments leveraging matroid axioms to ensure that dynamic updates preserve both independence and near-optimality.

One of the technicalities of this dynamic framework lies in its sampling size estimation procedure, which differs fundamentally from the binary-search sampling method used in [32], originally introduced in [33] and [20]. Due to the exchange property inherent in matroid constraints, this binary-search approach cannot be directly applied. Instead, we design a new sampling mechanism adapted to the matroid structure. For each layer ℓ\ell, to estimate the number of elements of the largest bucket that can be uniformly sampled all at once (i.e., non-adaptively), we consider a polylogarithmic number of random permutations of elements in the largest bucket. For each permutation, we iterate from its beginning to determine the elements that can be added to the current solution while maintaining independence. (Recall that if a conflict arises, elements currently in II are removed to restore feasibility, and the removed elements are added to I∪{I^{\cup}}. It is important to note that, unlike the dynamic algorithm for cardinality constraint [32], where marginal gains are compared directly against the current solution, in our matroid-constrained setting, the marginal gains are compared with respect to I∪{I^{\cup}}, while the independence condition is enforced relative to the solution set II.)

After processing all permutations, we identify the largest index ii of the permutations such that, in at least a (1−ϵ)(1-\epsilon)-fraction of the permutations, the element at index ii could be added to I∪{I^{\cup}}. Finally, in contrast to the cardinality-constrained setting, where all tt uniformly sampled elements from the largest bucket are added to the solution, our framework must verify each sampled element individually to ensure matroid feasibility.

However, the primary technical challenge of this work, distinguishing it from [11], arises from the fundamental structural disparities between matroids and matchings. Specifically, the \textsc{Inspect} and {\textsc{Adjust}} procedures required for matroids are more involved than those employed in the matching framework. These structural differences ultimately lead to a substantially different and more complex analysis to establish approximation guarantees.

Dynamic submodular maximization has attracted significant attention in recent years. Lattanzi et al. [34] presented a randomized dynamic algorithm that maintains a (2+ϵ)(2+\epsilon)-approximate solution for maximizing a monotone submodular function under a cardinality constraint kk. Their method achieves an amortized expected query complexity O(ϵ−11log⁡6(k)log⁡2(n))O(\epsilon^{-11} \log^6(k) \log^2(n)) per update, which is polylogarithmic in nn. Independently, Monemizadeh [22] developed another randomized dynamic algorithm with similar approximation guarantees, requiring O(ϵ−3k2log⁡5(n))O(\epsilon^{-3} k^2 \log^5(n)) queries per update. Subsequent work extended these results to the dynamic non-monotone setting [35]. Further advances demonstrated that near-optimal efficiency is achievable for related problems such as submodular cover [10] and maximum submodular matching [11], attaining polylogarithmic query complexity. However, achieving polylogarithmic update time for matroid constraints remains an open challenge despite persistent efforts [16, 38, 17, 34]. This paper resolves this open problem.

Chen and Peng [38] established lower bounds for dynamic submodular maximization with cardinality constraints, which is a special case of matroid constraints. They showed that any algorithm achieving better than a (2−ϵ)(2-\epsilon)-approximation must have amortized query complexity at least nΩ~(ϵ)/k3n^{\tilde{\Omega}(\epsilon)} / k^3, and achieving an approximation better than 1.7121.712 requires Ω(n/k3)\Omega(n / k^3) queries per update, even if the optimal value of the current set is known. In the insertion-only model, they further provided algorithms for submodular maximization under a matroid constraint of rank kk, achieving (2+ϵ)(2+\epsilon) and (ee−1+ϵ)(\frac{e}{e-1}+\epsilon)-approximations with expected oracle query complexity kO~(1/ϵ)k^{\tilde{O}(1/\epsilon)} and kO~(1/ϵ2)⋅log⁡(n)k^{\tilde{O}(1/\epsilon^2)} \cdot \log(n), respectively.

For general matroid constraints, Dütting et al. [17] proposed a (4+ϵ)(4+\epsilon)-approximation algorithm with expected amortized update time O ⁣(k2ϵlog⁡klog⁡nlog⁡3kϵ)O\!\bigl(\frac{k^2}{\epsilon} \log k \log n \log^3 \tfrac{k}{\epsilon}\bigr), which scales quadratically with the matroid rank kk. An improved method was later introduced by Banihashem et al. [16], which achieves a similar approximation ratio but with expected amortized update time O(klog⁡klog⁡3kϵ)O(k \log k \log^3 \tfrac{k}{\epsilon}), linear in kk. Although these results represent progress, both approaches become inefficient when kk is large (e.g., k=no(1)k = n^{o(1)}), since their complexity still grows polynomially in kk.

A related line of research considers the streaming setting, where the data arrives sequentially and algorithms must work with limited memory. The first streaming algorithm for submodular maximization under a cardinality constraint was proposed by Badanidiyuru et al. [15], who gave a (2+ϵ)(2+\epsilon)-approximation using O(kϵ−1log⁡k)O(k\epsilon^{-1} \log k) space. This was later improved by Kazemi et al. [21], who reduced the space requirement to O(kϵ−1)O(k\epsilon^{-1}). Chakrabarti and Kale [44] introduced a streaming framework applicable to a wide range of combinatorial constraints, including matroid and matching constraints. Their approach yields a 44-approximation algorithm for submodular maximization under a matroid constraint, using O(k)O(k) space.

Preliminaries

In this section, we introduce submodular functions, matroids, the oblivious adversarial model used in our dynamic setting, and the notion of query complexity.

Submodular functions.

Let N\mathcal{N} be a finite ground set. A function f:2N→R+f: 2^{\mathcal{N}} \rightarrow {\mathbb{R}}^+ is called submodular if for all A⊆B⊆NA \subseteq B \subseteq \mathcal{N} and any e∉Be \notin B, f(A∪{e})−f(A)≥f(B∪{e})−f(B),f(A \cup \{e\}) - f(A) \ge f(B \cup \{e\}) - f(B), capturing the principle of diminishing returns: the benefit of adding an element ee to a smaller set AA is at least as large as adding it to its supersets. An equivalent definition states that for all A,B⊆NA, B \subseteq \mathcal{N}, f(A)+f(B)≥f(A∪B)+f(A∩B),f(A) + f(B) \ge f(A \cup B) + f(A \cap B),. We assume that the submodular function ff is also monotone, meaning f(A∪{e})≥f(A)f(A \cup \{e\}) \ge f(A) for all A⊆NA \subseteq \mathcal{N}. The value f(A∪{e})−f(A)f(A \cup \{e\}) - f(A) is called the marginal gain of adding ee to AA, and is denoted by f(e∣A)f(e | A). In this paper, we assume to have access to ff via a value oracle.

Matroids.

References

  1. [1]Wu, H., Zhang, Y., Ma, C., Lyu, F., He, B., Mitra, B., & Liu, X. (2024). Result Diversification in Search and Recommendation: A Survey. IEEE Transactions on Knowledge and Data Engineering, 36(10), 5354–5373. https://doi.org/10.1109/TKDE.2024.3382262
  2. [2]Tang, H., Wu, S., Xu, G., & Li, Q. (2023). Dynamic Graph Evolution Learning for Recommendation. Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, 1589–1598. https://doi.org/10.1145/3539618.3591674
  3. [3]Guo, H., Sun, Z., Wang, D., Wei, T., Li, J., & Zhang, J. (2025). Enhancing New-item Fairness in Dynamic Recommender Systems. Proceedings of the 48th International ACM SIGIR Conference on Research and Development in Information Retrieval. https://doi.org/10.1145/3726302.3729969
  4. [4]Ma, Y., Narayanaswamy, M. B., Lin, H., & Ding, H. (2020). Temporal-Contextual Recommendation in Real-Time. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.
  5. [5]Tschiatschek, S., Djolonga, J., & Krause, A. (2016). Learning Probabilistic Submodular Diversity Models Via Noise Contrastive Estimation. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, 51, 770–779. https://proceedings.mlr.press/v51/tschiatschek16.htmlproceedings.mlr.press/v51/tschiatschek16.html
  6. [6]Krause, A., & Guestrin, C. (2011). Submodularity and its applications in optimized information gathering. ACM Trans. Intell. Syst. Technol., 2(4), 32:1–32:20. https://doi.org/10.1145/1989734.1989736
  7. [7]Kempe, D., Kleinberg, J. M., & Tardos, É. (2003). Maximizing the spread of influence through a social network. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 24 - 27, 2003, 137–146. https://doi.org/10.1145/956750.956769
  8. [8]Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A., Vondrák, J., & Krause, A. (2016). Fast constrained submodular maximization: Personalized data summarization. International Conference on Machine Learning (ICML), 1358–1367.
  9. [9]Hanauer, K., Henzinger, M., & Schulz, C. (2022). Recent Advances in Fully Dynamic Graph Algorithms - A Quick Reference Guide. ACM J. Exp. Algorithmics, 27, 1.11:1–1.11:45. https://doi.org/10.1145/3555806
  10. [10]Banihashem, K., Goudarzi, S., Hajiaghayi, M., Jabbarzade, P., & Monemizadeh, M. (2024). A Dynamic Algorithm for Weighted Submodular Cover Problem. Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. https://openreview.net/forum?id=uUeXaKLE1Iopenreview.net/forum?id=uUeXaKLE1I
  11. [11]Banihashem, K., Biabani, L., Goudarzi, S., Hajiaghayi, M., Jabbarzade, P., & Monemizadeh, M. (2025). Dynamic Algorithms for Submodular Matching. 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, July 8-11, 2025, Aarhus, Denmark, 334, 19:1–19:21. https://doi.org/10.4230/LIPICS.ICALP.2025.19
  12. [12]Wei, K., Iyer, R. K., & Bilmes, J. A. (2015). Submodularity in Data Subset Selection and Active Learning. Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, 37, 1954–1963. http://proceedings.mlr.press/v37/wei15.htmlproceedings.mlr.press/v37/wei15.html
  13. [13]Golovin, D., & Krause, A. (2010). Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimization. COLT 2010 - The 23rd Conference on Learning Theory, Haifa, Israel, June 27-29, 2010, 333–345. http://colt2010.haifa.il.ibm.com/papers/COLT2010proceedings.pdf\#page=341colt2010.haifa.il.ibm.com/papers/COLT2010proceedings.pdf\#page=341
  14. [14]Mossel, E., & Roch, S. (2007). On the submodularity of influence in social networks. Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, 128–134. https://doi.org/10.1145/1250790.1250811
  15. [15]Badanidiyuru, A., Mirzasoleiman, B., Karbasi, A., & Krause, A. (2014). Streaming submodular maximization: massive data summarization on the fly. The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '14, New York, NY, USA - August 24 - 27, 2014, 671–680. https://doi.org/10.1145/2623330.2623637
  16. [16]Banihashem, K., Biabani, L., Goudarzi, S., Hajiaghayi, M., Jabbarzade, P., & Monemizadeh, M. (2024). Dynamic Algorithms for Matroid Submodular Maximization. Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, 3485–3533. https://doi.org/10.1137/1.9781611977912.125
  17. [17]Dütting, P., Fusco, F., Lattanzi, S., Norouzi-Fard, A., & Zadimoghaddam, M. (2025). Fully Dynamic Submodular Maximization over Matroids. ACM Trans. Algorithms, 21(1), 11:1–11:23. https://doi.org/10.1145/3698397
  18. [19]Gharan, S. O., & Vondrák, J. (2013). On Variants of the Matroid Secretary Problem. Algorithmica, 67(4), 472–497. https://doi.org/10.1007/s00453-013-9795-y
  19. [20]Balkanski, E., Rubinstein, A., & Singer, Y. (2019). An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, 66–77. https://doi.org/10.1145/3313276.3316304
  20. [21]Kazemi, E., Mitrovic, M., Zadimoghaddam, M., Lattanzi, S., & Karbasi, A. (2019). Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity. Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, 97, 3311–3320. http://proceedings.mlr.press/v97/kazemi19a.htmlproceedings.mlr.press/v97/kazemi19a.html
  21. [22]Monemizadeh, M. (2020). Dynamic Submodular Maximization. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual. https://proceedings.neurips.cc/paper/2020/hash/6fbd841e2e4b2938351a4f9b68f12e6b-Abstract.htmlproceedings.neurips.cc/paper/2020/hash/6fbd841e2e4b2938351a4f9b68f12e6b-Abstract.html
  22. [23]Bateni, M., Chen, L., Esfandiari, H., Fu, T., Mirrokni, V. S., & Rostamizadeh, A. (2019). Categorical Feature Compression via Submodular Optimization. Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, 97, 515–523. http://proceedings.mlr.press/v97/bateni19a.htmlproceedings.mlr.press/v97/bateni19a.html
  23. [24]Liu, X., Ye, S., Fiumara, G., & De Meo, P. (2024). Influence Nodes Identifying Method via Community-Based Backward Generating Network Framework. IEEE Transactions on Network Science and Engineering, 11(1), 236–253. https://doi.org/10.1109/TNSE.2023.3295911
  24. [25]Chekuri, C., & Quanrud, K. (2021). Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Connectivity. 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), 198, 50:1–50:20. https://doi.org/10.4230/LIPICS.ICALP.2021.50
  25. [26]Chekuri, C., & Quanrud, K. (2019). Submodular Function Maximization in Parallel via the Multilinear Relaxation. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, 303–322. https://doi.org/10.1137/1.9781611975482.20
  26. [27]Guo, J., & Wu, W. (2020). Influence Maximization: Seeding Based on Community Structure. ACM Trans. Knowl. Discov. Data, 14(6). https://doi.org/10.1145/3399661
  27. [28]Feldman, M., Svensson, O., & Zenklusen, R. (2015). A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem. Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, 1189–1201. https://doi.org/10.1137/1.9781611973730.79
  28. [29]Lachish, O. (2014). O(log log Rank) Competitive Ratio for the Matroid Secretary Problem. 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, 326–335. https://doi.org/10.1109/FOCS.2014.42
  29. [30]Im, S., & Wang, Y. (2011). Secretary Problems: Laminar Matroid and Interval Scheduling. Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, 1265–1274. https://doi.org/10.1137/1.9781611973082.96
  30. [31]Korula, N., & Pál, M. (2009). Algorithms for Secretary Problems on Graphs and Hypergraphs. Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part II, 5556, 508–520. https://doi.org/10.1007/978-3-642-02930-1\_42
  31. [32]Banihashem, K., Biabani, L., Goudarzi, S., Hajiaghayi, M., Jabbarzade, P., & Monemizadeh, M. (2023). Dynamic Constrained Submodular Optimization with Polylogarithmic Update Time. International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, 202, 1660–1691. https://proceedings.mlr.press/v202/banihashem23a.htmlproceedings.mlr.press/v202/banihashem23a.html
  32. [33]Fahrbach, M., Mirrokni, V. S., & Zadimoghaddam, M. (2019). Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, 255–273. https://doi.org/10.1137/1.9781611975482.17
  33. [34]Lattanzi, S., Mitrovic, S., Norouzi-Fard, A., Tarnawski, J., & Zadimoghaddam, M. (2020). Fully Dynamic Algorithm for Constrained Submodular Optimization. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual. https://proceedings.neurips.cc/paper/2020/hash/9715d04413f296eaf3c30c47cec3daa6-Abstract.htmlproceedings.neurips.cc/paper/2020/hash/9715d04413f296eaf3c30c47cec3daa6-Abstract.html
  34. [35]Banihashem, K., Biabani, L., Goudarzi, S., Hajiaghayi, M., Jabbarzade, P., & Monemizadeh, M. (2023). Dynamic Non-monotone Submodular Maximization. Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023. http://papers.nips.cc/paper\_files/paper/2023/hash/387982dbf23d9975c7fc45813dd3dabc-Abstract-Conference.htmlpapers.nips.cc/paper\_files/paper/2023/hash/387982dbf23d9975c7fc45813dd3dabc-Abstract-Conference.html
  35. [36]Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978). An analysis of approximations for maximizing submodular set functions - I. Math. Program., 14(1), 265–294. https://doi.org/10.1007/BF01588971
  36. [37]Banihashem, K., Goudarzi, S., Hajiaghayi, M., Jabbarzade, P., & Monemizadeh, M. (n.d.). A Dynamic Algorithm for Weighted Submodular Cover Problem. Forty-first International Conference on Machine Learning.
  37. [38]Chen, X., & Peng, B. (2022). On the complexity of dynamic submodular maximization. STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, 1685–1698. https://doi.org/10.1145/3519935.3519951
  38. [39]Babaioff, M., Immorlica, N., & Kleinberg, R. (2007). Matroids, secretary problems, and online mechanisms. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, 434–443. http://dl.acm.org/citation.cfm?id=1283383.1283429dl.acm.org/citation.cfm?id=1283383.1283429
  39. [41]Hanauer, K., Henzinger, M., & Schulz, C. (2022). Recent Advances in Fully Dynamic Graph Algorithms (Invited Talk). 1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2022, March 28-30, 2022, Virtual Conference, 221, 1:1–1:47. https://doi.org/10.4230/LIPIcs.SAND.2022.1
  40. [42]Chen, L., Esfandiari, H., Fu, G., Mirrokni, V. S., & Yu, Q. (2021). Feature Cross Search via Submodular Optimization. 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), 204, 31:1–31:16. https://doi.org/10.4230/LIPICS.ESA.2021.31
  41. [43]Carter, L., & Wegman, M. N. (1977). Universal Classes of Hash Functions (Extended Abstract). Proceedings of the 9th Annual ACM Symposium on Theory of Computing, May 4-6, 1977, Boulder, Colorado, USA, 106–112. https://doi.org/10.1145/800105.803400
  42. [44]Chakrabarti, A., & Kale, S. (2015). Submodular maximization meets streaming: Matchings, matroids, and more. Mathematical Programming, 154(1), 225–247.
  43. [45]Ezra, T., Feldman, M., Gravin, N., & Tang, Z. G. (2020). Secretary matching with general arrivals. https://arxiv.org/abs/2011.01559

Paper details

vlnc:W_e333sbnw
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents