Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

DOI10.1007/978-3-642-03685-9_19MaRDI QIDQ5902164zbMATH OpenOpenAlexFDO

Authors Jon Lee, Maxim Sviridenko, Jan Vondrák

Publication date 28 October 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03685-9_19

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Submodular maximization over multiple matroids via generalized exchange properties
• A vector exchange property of submodular systems
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• scientific article; zbMATH DE number 4181354
• A new exchange property for matroids and its application to max-min-problems
• Maximization of k-submodular function with a matroid constraint
• Non-monotone submodular maximization under matroid and knapsack constraints
• An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• scientific article; zbMATH DE number 1953186

Cited in

(7)

• A note on submodularity preserved involving the rank functions
• Distributed submodular maximization
• Nonmonotone submodular maximization via a structural continuous greedy algorithm (extended abstract)
• Improved competitive ratios for submodular secretary problems (extended abstract)
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• Stability and recovery for independence systems
• Submodular maximization over multiple matroids via generalized exchange properties

This page was built for publication: Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

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