Lune

SODA2021Top-tier venue

Beyond Submodular Maximization via One-Sided Smoothness

Mehrdad Ghadiri, Richard Santiago, F. Bruce Shepherd

Abstract

The multilinear framework was developed to achieve the breakthrough 1 -1/e approximation for maximizing a monotone submodular function subject to a matroid constraint, which includes the submodular welfare problem as special case. This framework has a continuous optimization part (solving the multilinear extension of a submodular set function) and a rounding part (rounding a fractional solution to an integral one). We extend both parts so that the resulting generalized framework may be used on a wider array of problems. In particular, we make a conceptual contribution by identifying a family of parameterized functions and their applications. As a running example we focus on solving diversity problems max f (S) = 1 2 i,j∈A A ij : S ∈ M, where M is matroid. These diversity functions have A ij ≥ 0 as a measure of dissimilarity of i, j, and A has 0-diagonal. This family of problems ranges from intractable problems such as densest k-subgraph, to 1 2 -approximable metric diversity problems. The multilinear extension F of such diversity functions satisfies ∇ 2 F (x) = A ≥ 0 and hence the original multilinear framework (which assumes non-positive Hessians) does not directly apply. Instead we introduce a new parameter for functions F ∈ C 2 which measures the approximability of the associated problem maxF (x) : x ∈ P , for solvable downwards-closed polytopes

for all u, x ≥ 0, x = 0. For σ = 0 this class includes previously studied classes such as continuous DR-submodular functions, and much more. For the multlinear extension of a diversity function, we show that it is one-sided σ-smooth whenever A ij forms a σ-semi-metric.

We give an Ω(1/σ)-approximation for the continuous maximization problem of monotone, normalized one-sided σ-smooth F with an additional property: non-positive third order partial derivatives. Since the multilinear extension of a diversity function has this additional property we can apply the extended multilinear framework to this family of discrete problems. This requires new matroid rounding techniques for quadratic objectives. The result is a Ω(1/σ 3/2 )approximation for maximizing a σ-semi-metric diversity function subject to matroid constraint. This improves upon the previous best bound of Ω(1/σ 2 ) and we give evidence that it may be tight. For general one-sided smooth functions, we show the continuous process gives an Ω(1/3 2σ )approximation, independent of n. In this setting, by discretizing, we present a concrete poly-time algorithm for multilinear functions that satisfy the one-sided σ-smoothness condition. We also describe a discretization for one-sided smooth functions with L-Lipschitz gradients.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

5 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Robustness in Multi-Objective Submodular Optimization: a Quantile Approach cites A Parameterized Family of Meta-Submodular Functions
  • Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection cites A Parameterized Family of Meta-Submodular Functions
  • Using Partial Monotonicity in Submodular Maximization cites A Parameterized Family of Meta-Submodular Functions
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers5

  1. Using Partial Monotonicity in Submodular MaximizationLoay Mualem, Moran FeldmanNeurIPS 2022 · 13 citations
  2. Neural Estimation of Submodular Functions with Applications to Differentiable Subset SelectionAbir De, Soumen ChakrabartiNeurIPS 2022 · 10 citations
  3. Robustness in Multi-Objective Submodular Optimization: a Quantile ApproachCédric Malherbe, Kevin ScamanICML 2022 · 3 citations
  4. Online and Bandit Algorithms Beyond ℓp NormsThomas Kesselheim, Marco Molinaro, Sahil SinglaSODA 2023 · 2 citations
  5. A Parameterized Family of Meta-Submodular FunctionsMehrdad Ghadiri, Richard Santiago, F. Bruce ShepherdSODA 2024

Related papers

  1. Improved Approximation Algorithms for k-Submodular Maximization via Multilinear ExtensionHuanjian Zhou, Lingxiao Huang, Baoxiang WangICLR 2025
  2. Extending the Extension: Deterministic Algorithm for Non-monotone Submodular MaximizationNiv Buchbinder, Moran FeldmanSTOC 2025 · 2 citations
  3. Constrained Submodular Maximization via New Bounds for DR-Submodular FunctionsNiv Buchbinder, Moran FeldmanSTOC 2024 · 16 citations
  4. A Constant-Factor Approximation for Nash Social Welfare with Subadditive ValuationsShahar Dobzinski, Wenzheng Li, Aviad Rubinstein, Jan VondrákSTOC 2024 · 3 citations
  5. Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone Submodular MaximizationAlan KuhnleAAAI 2021 · 18 citations
Dusk over the sea between two cliffs drawn in fine vertical lines