Weakly Submodular Function Maximization Using Local Submodularity Ratio.

DOI10.4230/LIPICS.ISAAC.2020.64MaRDI QIDQ6065474zbMATH OpenOpenAlexFDO

Authors Richard Santiago, Yuichi Yoshida

Publication date 14 November 2023

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

zbMATH Keywords

local submodularity rationon-monotoneweakly submodular

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: Weak submodularity is a natural relaxation of the diminishing return property, which is equivalent to submodularity. Weak submodularity has been used to show that many (monotone) functions that arise in practice can be efficiently maximized with provable guarantees. In this work we introduce two natural generalizations of weak submodularity for non-monotone functions. We show that an efficient randomized greedy algorithm has provable approximation guarantees for maximizing these functions subject to a cardinality constraint. We then provide a more refined analysis that takes into account that the weak submodularity parameter may change (sometimes improving) throughout the execution of the algorithm. This leads to improved approximation guarantees in some settings. We provide applications of our results for monotone and non-monotone maximization problems.

Cites work

• A Unified Continuous Greedy Algorithm for Submodular Maximization
• An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs
• Approximate submodularity and its applications: subset selection, sparse approximation and dictionary selection
• Approximation algorithms for maximum dispersion
• Capturing complementarity in set functions by going beyond submodularity/subadditivity
• Constrained submodular maximization via a nonsymmetric technique
• Heuristic and Special Case Algorithms for Dispersion Problems
• Max-sum diversification, monotone submodular functions, and dynamic updates
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Restricted strong convexity implies weak submodularity
• Submodular maximization by simulated annealing
• Submodular maximization with cardinality constraints
• Symmetry and approximability of submodular maximization problems
• Welfare maximization and the supermodular degree

Cited in

(3)

• Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint
• Greedy algorithm for maximization of semi-monotone non-submodular functions with applications
• Approximation algorithm of maximizing non-submodular functions under non-submodular constraint

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065474)