A primal-dual algorithm for monotone submodular maximization

DOI10.1016/J.ORL.2025.107387MaRDI QIDQ7233029zbMATH OpenFDO

Authors Deeparnab Chakrabarty, Luc Cote

Publication date 24 April 2026

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.ORL.2025.107387

zbMATH Keywords

primal-dual algorithmssubmodular functions

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Cites work

• A new approximation guarantee for monotone submodular function maximization via discrete convexity
• An analysis of approximations for maximizing submodular set functions—I
• Approximating the least core value and least core of cooperative games with supermodular costs
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Fast algorithms for maximizing submodular functions
• scientific article; zbMATH DE number 3559283 (Why is no real title available?)
• scientific article; zbMATH DE number 3580314 (Why is no real title available?)
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies

This page was built for publication: A primal-dual algorithm for monotone submodular maximization

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