Unified Greedy Approximability beyond Submodular Maximization

DOI10.1137/22M1526952MaRDI QIDQ6141865zbMATH OpenOpenAlexWikidataFDO

Authors Y. Disser, David Weckbecker

Publication date 23 January 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/22m1526952

zbMATH Keywords

approximation ratioaugmentabilitycardinality-constrained maximizationgreedy algorithmindependence systemsubmodularity ratio

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cites work

• A note on maximizing a submodular set function subject to a knapsack constraint
• A THEOREM ON INDEPENDENCE RELATIONS
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• An analysis of approximations for maximizing submodular set functions—I
• An Analysis of the Greedy Heuristic for Independence Systems
• Approximate submodularity and its applications: subset selection, sparse approximation and dictionary selection
• Combinatorial optimization. Theory and algorithms.
• General bounds for incremental maximization
• Greedy algorithm and symmetric matroids
• Greedy in Approximation Algorithms
• scientific article; zbMATH DE number 5888315 (Why is no real title available?)
• scientific article; zbMATH DE number 5968956 (Why is no real title available?)
• scientific article; zbMATH DE number 3544074 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• Matroids and the greedy algorithm
• Maximizing a monotone submodular function subject to a matroid constraint
• Non-monotone submodular maximization under matroid and knapsack constraints
• Optimal approximation for the submodular welfare problem in the value oracle model
• Robust monotone submodular function maximization
• Structured Robust Submodular Maximization: Offline and Online Algorithms
• Submodular maximization with cardinality constraints
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• The design of approximation algorithms
• Unified greedy approximability beyond submodular maximization

Cited in

(5)

• On positive influence dominating sets with bi-directional weighted constraint in social networks
• Incremental-decremental maximization
• Non-submodular maximization subject to a knapsack constraint on the integer lattice
• Incremental maximization for a broad class of objectives
• Incremental-decremental maximization

This page was built for publication: Unified Greedy Approximability beyond Submodular Maximization

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