mlsanityData to 14 Oct 2026

A Note On Deterministic Submodular Maximization With Bounded Curvature

arXiv 2409.02943 ↗First posted 25 Aug 2024cs.DS cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We show that the recent breakthrough result of [Buchbinder and Feldman, FOCS'24] could further lead to a deterministic (1-kappaf/e-varepsilon)-approximate algorithm for maximizing a submodular function with curvature kappaf under matroid constraint.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 6 of its 7 references that are in the map. First posted on arXiv 25 Aug 2024.

Builds on

6 of 7 references.

References · 6

  1. 2013Optimal approximation for submodular and supermodular optimization with bounded curvaturecited by 29
  2. 2019Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applicationscited by 21
  3. 2015Deterministic Algorithms for Submodular Maximization Problemscited by 10
  4. 2020Submodular Maximization in Clean Linear Timecited by 10
  5. 2024Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraintcited by 6
  6. 2018Deterministic (1/2 + ε)-Approximation for Submodular Maximization over a Matroidcited by 1

Built on by

Not cited yet.