Weakly Submodular Function Maximization Using Local Submodularity Ratio.

DOI10.4230/lipics.isaac.2020.64arXiv2004.14650OpenAlexW3115852453MaRDI QIDQ6065474

Richard Santiago, Yuichi Yoshida

Publication date: 14 November 2023

Full work available at URL: https://arxiv.org/abs/2004.14650

zbMATH Keywords

non-monotonelocal submodularity ratioweakly submodular

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (1)

Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for maximum dispersion
• Restricted strong convexity implies weak submodularity
• An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs
• Symmetry and Approximability of Submodular Maximization Problems
• Welfare maximization and the supermodular degree
• Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
• Heuristic and Special Case Algorithms for Dispersion Problems
• Max-Sum Diversification, Monotone Submodular Functions, and Dynamic Updates
• Constrained Submodular Maximization via a Nonsymmetric Technique
• Submodular Maximization with Cardinality Constraints
• A Unified Continuous Greedy Algorithm for Submodular Maximization

This page was built for publication: Weakly Submodular Function Maximization Using Local Submodularity Ratio.