Weak submodularity implies localizability: local search for constrained non-submodular function maximization

DOI10.1016/J.DISC.2024.114287MaRDI QIDQ6646409FDOQ6646409

Authors: Majun Shi, Qingyong Zhu, Bei Liu, Yu-Chao Li 

Publication date: 2 December 2024

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

local searchlocalizability\(p\)-matroidnon-submodular functionweak submodularity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Mathematical programming (90Cxx) Designs and configurations (05Bxx)

Cites Work

• Title not available (Why is that?)
• Monotone submodular maximization over a matroid via non-oblivious local search
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Maximizing a monotone submodular function subject to a matroid constraint
• An analysis of approximations for maximizing submodular set functions—I
• Submodular maximization over multiple matroids via generalized exchange properties
• Optimal approximation for the submodular welfare problem in the value oracle model
• A \(\frac{(k+3)}{2}\)-approximation algorithm for monotone submodular \(k\)-set packing and general \(k\)-exchange systems
• Maximize a monotone function with a generic submodularity ratio
• Greedy guarantees for non-submodular function maximization under independent system constraint with applications
• Greedy is good: constrained non-submodular function maximization via weak submodularity

This page was built for publication: Weak submodularity implies localizability: local search for constrained non-submodular function maximization

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