mlsanityData to 14 Oct 2026

Submodular Maximization via Taylor Series Approximation

arXiv 2101.07423 ↗First posted 19 Jan 2021cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

We study submodular maximization problems with matroid constraints, in particular, problems where the objective can be expressed via compositions of analytic and multilinear functions. We show that for functions of this form, the so-called continuous greedy algorithm attains a ratio arbitrarily close to (1-1/e) ≈ 0.63 using a deterministic estimation via Taylor series approximation. This drastically reduces execution time over prior art that uses sampling.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 11 of its 45 references that are in the map. First posted on arXiv 19 Jan 2021.

Builds on

11 of 45 references.

References · 11

  1. 2014Lazier Than Lazy Greedycited by 99
  2. 2018Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximizationcited by 47
  3. 2017Gradient Methods for Submodular Maximizationcited by 33
  4. 2016Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domainscited by 31
  5. 2015Submodular Functions: from Discrete to Continous Domainscited by 25
  6. 2017Continuous DR-submodular Maximization: Structure and Algorithmscited by 24
  7. 2017Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gapcited by 21
  8. 2018Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximizationcited by 12
  9. 2017Stochastic Submodular Maximization: The Case of Coverage Functionscited by 11
  10. 2017Robust Budget Allocation via Continuous Submodular Functionscited by 8
  11. 2019Kelly Cache Networkscited by 3

Built on by

Cited by year

Citing papers per year: 2023: 1.

1 paper.

  1. 2023Stochastic Submodular Maximization via Polynomial Estimatorscited by 0