betaFeedback

WorksComputer Science

Consistent Submodular Maximization with Full Foresight

Abstract

Online algorithms with bounded recourse face three intertwined obstacles: uncertainty about the future, computational limits, and a limited budget for changes. We ask a fundamental question that separates consistency from the other two: what does solution stability cost when the entire future is known and computation is unlimited? We answer this question for monotone submodular maximization, where an algorithm must maintain a solution of at most kk arrived elements, with a constant number of changes per step. We determine the optimal approximation thresholds: 3/43/4 for deterministic algorithms and ξ⋆≈0.7942ξ^\star \approx 0.7942 for randomized algorithms. For every ε>0\varepsilon>0, we get within ε\varepsilon of these thresholds with worst-case recourse polynomial in 1/ε1/\varepsilon, independent of kk and the stream length. We prove matching impossibility results even for coverage functions. We attain the sharp bounds by optimally balancing two opposing forces: preparing for future arrivals and protecting the current solution. For randomized algorithms, we use addition robustness against prefixes of the known future, which we analyze tightly via an interval-selection problem. For deterministic algorithms, we introduce certificates, paths in a fractional relaxation that maintain high value, which we round into an update schedule.

Introduction

Online algorithms with recourse have emerged as a central paradigm for optimization over evolving inputs: they maintain good solutions as the input changes, while limiting how much these solutions change, either at each update or in aggregate over the entire sequence. This paradigm has been developed for a broad range of fundamental problems, including Steiner trees [32, 29], minimum spanning trees and TSP [36], scheduling [40], bin packing [24], set cover [31], bipartite matching [10, 7], kk-clustering [34, 26], and submodular maximization [19, 20].

Such algorithms face three intertwined obstacles: uncertainty about the future, computational limits, and a limited budget for changes. Approximation guarantees reflect the joint effect of all three, so they do not reveal what stability itself costs. Isolating this cost requires removing the other two obstacles, which leads to the following question:

How much solution quality must be sacrificed to maintain stability when the entire future is known and computation is unlimited?

We study this question for monotone submodular maximization under a cardinality constraint [33] (Nemhauser et al. 1978). We give the algorithm full knowledge of the arrival sequence and unrestricted computational power. Each maintained solution must use only elements that have already arrived, and consecutive solutions may differ by only a constant number of elements. Even with full foresight, preparing a solution for future arrivals can compromise its current value, while postponing changes can leave too little time to complete them. The challenge is to plan solutions and transitions that remain close to the current optimum while respecting the recourse bound.

The Model

Let f:2X→R≥0f : 2^{X} \to\mathbb{R}_{\ge0} be a monotone submodular function accessible through value queries, and let k≥1k \ge1 be an integer cardinality bound. Elements x1,…,xn∈Xx_1,\ldots,x_n \in X arrive one at a time, and the algorithm knows the entire arrival sequence in advance. After the tt-th arrival, the algorithm must maintain a solution ALGt⊆Xt\mathrm{ALG}_t \subseteq X_t, where Xt={x1,…,xt}X_t = \{x_1,\ldots,x_t\}, satisfying ∣ALGt∣≤k|\mathrm{ALG}_t| \le k for every realization of its randomness. We set ALG0=∅\mathrm{ALG}_0 = \varnothing and let OPTt\mathrm{OPT}_t denote a set maximizing f(S)f(S) over all S⊆XtS \subseteq X_t with ∣S∣≤k|S| \le k. Computation and the number of value queries are unrestricted, and queries may involve elements that have not yet arrived.

We evaluate a possibly randomized algorithm according to two guarantees:

  • Approximation. For α≤1\alpha\le1, an algorithm is an α\alpha-approximation if, on every instance and at every time tt, E[f(ALGt)]≥αf(OPTt)\mathbb{E}[f(\mathrm{ALG}_t)] \ge\alpha f(\mathrm{OPT}_t). The expectation is over the algorithm’s internal randomness, with the instance and time tt fixed; the guarantee need not hold simultaneously at all times for a single realization. For deterministic algorithms, we use f(ALGt)f(\mathrm{ALG}_t) instead of E[f(ALGt)]\mathbb{E}[f(\mathrm{ALG}_t)].

  • Consistency. An algorithm is CC-consistent if, on every instance and for every realization of its randomness, ∣ALGt△ALGt−1∣≤C|\mathrm{ALG}_t \mathbin{\triangle} \mathrm{ALG}_{t-1}| \le C for all t=1,…,nt = 1,\ldots,n. Here △\triangle denotes the symmetric difference.1 An algorithm is consistent if it is CC-consistent for some constant CC independent of the input instance, including kk and nn. For algorithms parameterized by an accuracy ε>0\varepsilon> 0, the constant CC may depend on ε\varepsilon.

We allow arbitrary constant recourse budgets to identify approximation barriers that persist for every fixed number of changes permitted per arrival.

Apart from the algorithm’s knowledge of the arrival sequence, this is the model of consistent submodular maximization introduced by Dütting et al. [ [19] and further studied by Dütting et al. [ [20] and Fu et al. [ [28], in which each element is revealed only upon arrival.2 We refer to their setting as non-clairvoyant and to ours as clairvoyant.

Results and Techniques

We establish tight information-theoretic bounds for consistent clairvoyant algorithms, both deterministic and randomized.

For randomized algorithms we show:

Main Result 1 (Tight randomized bound; see Thm. 1 & Thm. 2). For every ε∈(0,1)\varepsilon\in(0,1), there is a randomized clairvoyant algorithm for monotone submodular maximization under a cardinality constraint that is O(ε−2)O(\varepsilon^{-2})-consistent and achieves a (ξ⋆−ε)(\xi^\star-\varepsilon)-approximation, where ξ⋆≈0.7942\xi^\star\approx0.7942.‡ No consistent randomized clairvoyant algorithm can achieve an approximation ratio greater than ξ⋆\xi^\star, even for coverage functions.

For this result, we handle transitions through the addition-robustness framework of Dütting et al. [ [20]. The algorithm periodically samples a new set of elements that have already arrived and transitions to it at a random time, so that any fixed time is rarely affected. This framework reduces the problem to constructing an addition-robust distribution, whose samples stay competitive in expectation as new elements arrive.

Foresight changes the nature of this task: the upcoming arrivals are known, but a single distribution must still be good at all times. Via minimax duality, as in the non-clairvoyant setting, it suffices to compare a single solution, fixed in advance, with the best choice in hindsight when the evaluation time is random. Our key insight is that, because the future arrival prefixes form a known nested sequence, this question can be cast as an interval-selection problem, quite different from the correlation-gap question that arises without foresight [20].

We solve this problem exactly. The crux is to show that the worst case consists of only three consecutive intervals, corresponding to just two future insertions; optimizing over such instances yields ξ⋆\xi^\star. The same analysis yields both bounds at once: every instance admits a robust distribution that is ξ⋆\xi^\star-competitive, and the worst case translates directly into a family of coverage instances that rules out a better approximation ratio for consistent algorithms.

For deterministic algorithms we show:

Main Result 2 (Tight deterministic bound; see Thm. 3 & Thm. 4). For every ε∈(0,1)\varepsilon\in(0,1), there is a deterministic clairvoyant algorithm for monotone submodular maximization under a cardinality constraint that is O(ε−3log⁡(1/ε))O(\varepsilon^{-3}\log(1/\varepsilon))-consistent and achieves a (3/4−ε)(3/4-\varepsilon)-approximation. No consistent deterministic clairvoyant algorithm can achieve an approximation ratio greater than 3/43/4, even for coverage functions.

The randomized construction places transitions at random times, so that any fixed time is affected by a transition only with small probability. A deterministic algorithm must maintain its approximation guarantee throughout each transition. A simple coverage construction makes this obstacle concrete: the algorithm is forced to move gradually from the rows of a k×kk \times k grid to increasingly valuable columns. Halfway through, its k/2k/2 rows and k/2k/2 columns cover only 3/43/4 of the grid, while the optimal solution covers all of it.

Obtaining the matching algorithmic guarantee requires a way to construct safe transitions. We introduce a framework of clairvoyant certificates, which combines a fractional solution that remains valuable throughout a window of arrivals with a transition path of controlled complexity connecting the initial and final optimizers through that solution. The entry and exit portions satisfy the required value guarantees under the initial and final objectives, respectively. A certificate thus balances preparing for future arrivals against protecting the current solution. The main technical contribution is a reduction that rounds the entire transition path simultaneously, preserving the required value guarantees while controlling the number of changes. The rounding argument establishes the existence of a single realization satisfying all requirements, which can be found deterministically by exhaustive search. Scheduling the resulting changes then yields a consistent algorithm with an arbitrarily small loss in approximation.

This framework reduces the algorithmic problem to establishing the existence of suitable fractional certificates. We give an elementary construction at level 1/2>1−1/e1/\sqrt{2} > 1 - 1/e that illustrates the framework, and prove in Lean that every window admits a certificate at the sharp level 3/43/4, yielding the optimal deterministic guarantee.

Discussion

Discussion. Even with full foresight and unrestricted computation, constant recourse imposes a strict approximation loss. Our results quantify this loss exactly and show that randomization remains beneficial in the absence of uncertainty about future arrivals. Figure 1 compares our thresholds with those for non-clairvoyant algorithms: foresight raises the deterministic threshold from at most 1/21/2 [19] to 3/43/4, and the randomized threshold from 2/32/3 to ξ⋆\xi^\star for submodular functions and from 3/43/4 to ξ⋆\xi^\star for coverage functions [20]. Without foresight, randomized algorithms do better on coverage functions than on general submodular functions; with foresight, the two classes have the same thresholds.

Overview of results

Figure 1. Overview of results. A single value is a tight threshold; an interval gives the best known lower and upper bounds. Poly time refers to algorithms that make polynomially many value queries and run in polynomial time, and info-theoretic to algorithms with unrestricted computation. The upper bound of 1−1/e1-1/e in polynomial time holds even without consistency constraints [39, 23].

Open Problems

Open Problems. Both of our thresholds exceed 1−1/e1 - 1/e, the best ratio achievable efficiently even without stability constraints [39, 23]. Can efficient clairvoyant algorithms with constant recourse approach 1−1/e1 - 1/e, so that stability costs nothing beyond computation? This would require exploiting foresight: without it, deterministic algorithms cannot exceed 1/21/2 [19], and efficient randomized algorithms cannot exceed 2−22 - \sqrt{2} [28]. The information-theoretic threshold for deterministic non-clairvoyant algorithms also remains open, between 0.3818 and 1/2 [19]. More broadly, it would be interesting to determine the cost of stability for the other problems and constraints studied with recourse.

Related Work

Consistent Submodular Maximization. In the non-clairvoyant setting, Dütting et al. [2024] gave a deterministic (0.3818−ε)(0.3818-\varepsilon)-approximation with constant recourse and showed that no consistent deterministic algorithm can exceed 1/21/2. Dütting et al. [2025] introduced addition robustness and a randomized checkpointing reduction, and determined the information-theoretic thresholds for randomized algorithms: 2/32/3 for monotone submodular functions and 3/43/4 for coverage functions. Fu et al. [2026] showed that 2−22-\sqrt{2} is the best ratio achievable with polynomially many value queries. Dütting et al. [2026] studied consistency in the fully dynamic setting, with both insertions and deletions. A different notion of stability underlies the submodular objectives chasing problem of Buchbinder et al. [2025], in which both the objective and the ground set change over time: their algorithms maintain a (1−1/e−ε)(1-1/e-\varepsilon)-approximation while keeping the total recourse competitive with that of exact offline algorithms. In contrast, we bound the recourse of every step by a constant.

Incremental and Multistage Optimization. Several models study how solutions evolve when the input is known in advance. In incremental maximization, the solutions for increasing budgets must be nested, and each must be competitive for its own budget [8, 16]; for submodular functions under increasing cardinality constraints, the greedy algorithm achieves 1−1/e1-1/e, and Bienkowski et al. [2026] recently improved on it. In incremental-decremental maximization, an initial solution is transformed one element at a time, and the order must keep every intermediate stage competitive with the optimum for that stage [17]. In multistage optimization, a sequence of instances is given, and the quality of each stage’s solution is traded off against the cost of changing it, or the changes between consecutive stages are bounded [30, 22, 1, 5, 27]. In our model, by contrast, the cardinality is fixed while the ground set grows, every solution must approximate the current optimum, and only a constant number of elements may change per arrival.

Streaming, Preemptive, and Dynamic Submodular Maximization. Streaming submodular maximization [13, 2, 25] focuses on bounding working memory (O(klog⁡k/ε)(O(k \log k/\varepsilon) for a (1/2−ε)(1/2-\varepsilon)-approximation) rather than solution stability. Buchbinder et al. [2019], Chan et al. [2018] study online submodular maximization under cardinality constraints with preemption but no recall. Fully dynamic submodular maximization under insertions and deletions [35, 37, 15, 18, 6] optimizes query update time; however, dynamic algorithms can achieve polylogarithmic expected amortized update time while still incurring Ω(k)\Omega(k) worst-case recourse during rebuild steps.

Online Algorithms with Bounded Recourse. Maintaining solutions with bounded recourse has been widely studied for combinatorial problems including Steiner trees [32], set cover [31], kk-clustering [34, 26], and matching [7]. Studying clairvoyant (offline dynamic) counterparts of online recourse problems separates the intrinsic cost of smooth transitions from online uncertainty; our results show that for submodular maximization, step-by-step consistency imposes a fundamental approximation barrier even under full foresight.

The Tight Randomized Bound

The optimal approximation ratio for randomized clairvoyant algorithms with a consistency bound independent of the cardinality constraint is ξ⋆≈0.794\xi^\star\approx0.794 for both coverage and monotone submodular functions, where ξ⋆\xi^\star is the unique4 root in (1/2,1)(1/2,1) of the polynomial

Ψ(ξ)=89ξ4−44ξ3−19ξ2−3ξ+1.\Psi(\xi) = 89\xi^4 - 44\xi^3 - 19\xi^2 - 3\xi+ 1.

We give the impossibility result in § 4.1 using a simple hard instance, then obtain a matching algorithmic guarantee in § 4.2–§ 4.5 by showing that this instance is a worst-case instance. The proofs for this section are deferred to Appendix § 8.

The Impossibility Result for Randomized Algorithms

Quite surprisingly, there is a very simple hard-instance construction based on only two insertions which yields this impossibility result for possibly randomized consistent algorithms. Moreover, the instance is based on a coverage function, thus showing—together with the matching algorithm—that there is no separation between coverage and monotone submodular functions. We state the result and provide a proof sketch, while the details can be found in Section A.2.

Theorem 1. For any ε∈[1/k,1]\varepsilon\in[1/k,1], no randomized εk\varepsilon k-consistent clairvoyant algorithm can achieve an approximation ratio better than ξ⋆+O(ε)≈0.7942+O(ε)\xi^\star+ O(\varepsilon) \approx0.7942 + O(\varepsilon) for Maximum Coverage subject to a cardinality constraint kk.

Proof sketch. We describe a weighted coverage instance on which every randomized εk\varepsilon k-consistent clairvoyant algorithm has approximation ratio at most ξ⋆+O(ε)\xi^\star+ O(\varepsilon). Appendix § 8.§ 4 converts it to an unweighted instance. Partition a universe UU of 3k3k elements into groups U0U_0, U1U_1, U2U_2 of kk elements each, with respective element weights 1>u1>u2>01 > u_1 > u_2 > 0. The arrival sequence consists of the 3k3k singleton subsets of UU, followed by the two large sets U0U_0 and U1U_1, in that order. Thus the sequence contains 3k+23k+2 sets; the singleton sets may arrive in any order. Figure 2 illustrates the construction.

Figure 2. The hard coverage instance for the randomized lower bound.

Relabel the last three time steps as 0, 1, and 2: immediately before U0U_0 arrives, immediately after U0U_0 arrives, and immediately after U1U_1 arrives. Let kik_i be the expected number of singleton sets from UiU_i in the algorithm’s solution at time 0. These counts suffice to bound the algorithm’s expected value at all three time steps: we include each large set in the algorithm’s solution as soon as it arrives, without counting it toward the cardinality constraint, and consistency limits the algorithm to at most εk\varepsilon k additional singleton sets per insertion. Since every singleton has weight at most 1, these additions contribute only O(εk)O(\varepsilon k) to its value.

In this sketch, we omit the O(εk)O(\varepsilon k) contribution of these additional singleton sets to the value of the solutions of the algorithm and assume the large sets also do not count toward the cardinality constraint for the optimal solutions. With these simplifications, the algorithm’s expected values at time steps 0, 1, and 2 are at most k0+u1k1+u2k2k_0 + u_1k_1 + u_2k_2, k+u1k1+u2k2k + u_1k_1 + u_2k_2, and k(1+u1)+u2k2k(1 + u_1) + u_2k_2. The corresponding optimal values are kk, k(1+u1)k(1 + u_1), and k(1+u1+u2)k(1 + u_1 + u_2). We can thus bound the optimal approximation ratio with the following LP.

Maximizeρsubject tok0+k1+k2≤k,k0+u1k1+u2k2≥ρ⋅k,k+u1k1+u2k2≥ρ(1+u1)⋅k,k(1+u1)+u2k2≥ρ(1+u1+u2)⋅k,ki≥0for i=0,1,2.\begin{aligned} \text{Maximize}\quad& \rho\\ \text{subject to}\quad& k_0 + k_1 + k_2 \le k, \\ & k_0 + u_1k_1 + u_2k_2 \ge\rho\cdot k, \\ & k + u_1k_1 + u_2k_2 \ge\rho(1 + u_1) \cdot k, \\ & k(1 + u_1) + u_2k_2 \ge\rho(1 + u_1 + u_2) \cdot k, \\ & k_i \ge0 \quad\text{for } i = 0,1,2. \end{aligned}

References

  1. [1]Hyung-Chan An, Ashkan Norouzi-Fard, and Ola Svensson. Dynamic facility location via exponential clocks. ACM Trans. Algorithms, 13(2):21:1–21:20, 2017.
  2. [2]Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Streaming submodular maximization: Massive data summarization on the fly. In KDD, pages 671–680, 2014.
  3. [3]Eric Balkanski, Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson, and Morteza Zadimoghaddam. Lean certificates for consistent submodular maximization with full foresight. GitHub repository, https://github.com/epfl-thl2/project-consistent-submodular-full-foresight, 2026a.DOI
  4. [4]Eric Balkanski, Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson, and Morteza Zadimoghaddam. Arguments used for initial prompts for deterministic algorithm. GitHub repository, https://github.com/epfl-thl2/project-consistent-submodular-full-foresight/tree/main/docs/initial_deterministic_algorithm.pdf, 2026b.
  5. [5]Evripidis Bampis, Bruno Escoffier, Michael Lampis, and Vangelis Th. Paschos. Multistage matchings. In SWAT, pages 7:1–7:13, 2018.DOI
  6. [6]Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabb arzade, and Morteza Monemizadeh. Dynamic constrained submodular optimization with polylogarithmic update time. In ICML, volume 202, pages 1660–1691, 2023.arxiv.org/abs/2305.15192
  7. [7]Aaron Bernstein, Jacob Holm, and Eva Rotenberg. Online bipartite matching with amortized O(log² n) replacements. J. ACM, 66(5):371–3723, 2019.
  8. [8]Aaron Bernstein, Yann Disser, Martin Groß, and Sandra Himburg. General bounds for incremental maximization. Math. Program., 191(2):953–979, 2022.
  9. [10]Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, and Anna Zych. Online bipartite matching in offline time. In FOCS, pages 384–393, 2014.DOI
  10. [13]Amit Chakrabarti and Sagar Kale. Submodular maximization meets streaming: matchings, matroids, and more. Math. Program., 154(1-2):225–247, 2015.
  11. [15]Xi Chen and Binghui Peng. On the complexity of dynamic submodular maximization. In STOC, pages 1685–1698. ACM, 2022.arxiv.org/abs/2111.03198
  12. [16]Yann Disser, Max Klimm, Kevin Schewior, and David Weckbecker. Incremental maximization via continuization. In ICALP, pages 47:1–47:17, 2023.arxiv.org/abs/2305.01310
  13. [17]Yann Disser, Max Klimm, Annette Lutz, and Lea Strubberg. Incremental-decremental maximization. Acta Informatica, 63(3):31, 2026.arxiv.org/abs/2508.14516
  14. [18]Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, and Morteza Zadimoghaddam. Fully dynamic submodular maximization over matroids. In ICML, volume 202, pages 8821–8835, 2023.DOI
  15. [19]Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, and Morteza Zadimoghaddam. Consistent submodular maximization. In ICML, pages 11979–11991, 2024.arxiv.org/abs/2405.19977
  16. [20]Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson, and Morteza Zadimoghaddam. The cost of consistency: Submodular maximization with constant recourse. In STOC, pages 1406–1417. ACM, 2025.arxiv.org/abs/2412.02492
  17. [22]David Eisenstat, Claire Mathieu, and Nicolas Schabanel. Facility location in evolving metrics. In ICALP, pages 459–470, 2014.arxiv.org/abs/1403.6758
  18. [23]Uriel Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634–652, 1998.
  19. [24]Björn Feldkord, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit Kumar, Sören Richers, and David Wajc. Fully-dynamic bin packing with little repacking. In ICALP, pages 51:1–51:24, 2018.DOI
  20. [25]Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. The one-way communication complexity of submodular maximization with applications to streaming and robustness. In STOC, pages 1363–1374, 2020.
  21. [26]Hendrik Fichtenberger, Silvio Lattanzi, and Ashkan Norouzi-Fard. Consistent k-clustering for general metrics. In SODA, pages 2660–2678, 2021.arxiv.org/abs/2011.06888
  22. [27]Till Fluschnik, Rolf Niedermeier, Valentin Rohm, and Philipp Zschoche. Multistage vertex cover. Theory Comput. Syst., 66(2):454–483, 2022.
  23. [28]Shi Fu, Qixin Zhang, and Dacheng Tao. A sharp barrier for consistent submodular maximization: Any improvement over 2 − √2 entails exponential queries or linear recourse. CoRR, abs/2609.09986, 2026.arxiv.org/abs/2609.09986
  24. [29]Albert Gu, Anupam Gupta, and Amit Kumar. The power of deferral: Maintaining a constant-competitive Steiner tree online. SIAM J. Comput., 45(1):1–28, 2016.
  25. [30]Anupam Gupta, Kunal Talwar, and Udi Wieder. Changing bases: Multistage optimization for matroids and matchings. In ICALP, pages 563–575, 2014.
  26. [31]Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi. Online and dynamic algorithms for set cover. In STOC, pages 537–550. ACM, 2017.arxiv.org/abs/1611.05646
  27. [32]Makoto Imase and Bernard M. Waxman. Dynamic Steiner tree problem. SIAM J. Discrete Math., 4(3):369–384, 1991.DOI
  28. [33]Andreas Krause and Daniel Golovin. Submodular function maximization. In Lucas Bordeaux, Youssef Hamadi, and Pushmeet Kohli, editors, Tractability: Practical Approaches to Hard Problems, pages 71–104. Cambridge University Press, 2014.
  29. [34]Silvio Lattanzi and Sergei Vassilvitskii. Consistent k-clustering. In ICML, volume 70, pages 1975–1984, 2017.
  30. [35]Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Jakub Tarnawski, and Morteza Zadimoghaddam. Fully dynamic algorithm for constrained submodular optimization. In NeurIPS, 2020.DOI
  31. [36]Nicole Megow, Martin Skutella, José Verschae, and Andreas Wiese. The power of recourse for online MST and TSP. SIAM J. Comput., 45(3):859–880, 2016.
  32. [37]Morteza Monemizadeh. Dynamic submodular maximization. In NeurIPS, 2020.
  33. [39]George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approximations for maximizing submodular set functions—I. Math. Program., 14(1):265–294, 1978.DOI
  34. [40]Peter Sanders, Naveen Sivadasan, and Martin Skutella. Online scheduling with bounded migration. Math. Oper. Res., 34(2):481–498, 2009.
  35. [41]Jan Vondrak. A note on concentration of submodular functions, 2010. URL https://arxiv.org/abs/1005.2791.

Paper details

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

views · 10

downloads · 0

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

  • Computer Science

ChatGPT Astra, Claude Opus, Gemini Argon

View statement
Looking for related papers…
Contents