Greedy is good: constrained non-submodular function maximization via weak submodularity

DOI10.1007/S40305-022-00444-2MaRDI QIDQ6601966zbMATH OpenFDO

Authors Majun Shi, Wei Wang

Publication date 11 September 2024

Published in Journal of the Operations Research Society of China (Search for Journal in Brave)

zbMATH Keywords

greedy algorithm\(p\)-systemnon-submodular function\(p\)-extendible system\(p\)-matroid intersection

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Nonlinear programming (90C30)

Recommendations

• Greedy guarantees for non-submodular function maximization under independent system constraint with applications
• Maximization of constrained non-submodular functions
• Maximization of nonsubmodular functions under multiple constraints with applications
• Greedy algorithm for maximization of non-submodular functions subject to knapsack constraint
• Maximizing a monotone non-submodular function under a knapsack constraint

Cites work

• scientific article; zbMATH DE number 5888315 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• An analysis of approximations for maximizing submodular set functions—I
• Design and analysis of approximation algorithms
• Maximize a monotone function with a generic submodularity ratio
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Maximizing a monotone submodular function subject to a matroid constraint
• Monotone submodular maximization over a matroid via non-oblivious local search
• Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
• Non-submodular maximization on massive data streams
• Non-submodular maximization with matroid and knapsack constraints
• Optimal approximation for the submodular welfare problem in the value oracle model
• Parametric monotone function maximization with matroid constraints
• Restricted strong convexity implies weak submodularity
• Submodular functions and optimization.
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem

Cited in

(5)

• Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid
• Weak submodularity implies localizability: local search for constrained non-submodular function maximization
• Maximize a monotone function with a generic submodularity ratio
• Fast deterministic algorithms for non-submodular maximization with strong performance guarantees
• Unified greedy approximability beyond submodular maximization

This page was built for publication: Greedy is good: constrained non-submodular function maximization via weak submodularity

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