Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid

DOI10.1137/1.9781611975482.16zbMath1431.90125arXiv1807.05532OpenAlexW4255179538MaRDI QIDQ5236197

Mohit Garg, Moran Feldman, Niv Buchbinder

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.05532

zbMATH Keywords

deterministic algorithmsmatroidsubmodular optimization

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (18)

On maximizing the difference between an approximately submodular function and a linear function subject to a matroid constraint ⋮ Two-stage stochastic max-weight independent set problems ⋮ A multi-pass streaming algorithm for regularized submodular maximization ⋮ A mobile multi-agent sensing problem with submodular functions under a partition matroid ⋮ Analyzing Residual Random Greedy for monotone submodular maximization ⋮ Improved deterministic algorithms for non-monotone submodular maximization ⋮ Improved deterministic algorithms for non-monotone submodular maximization ⋮ Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid ⋮ Deterministic approximation algorithm for submodular maximization subject to a matroid constraint ⋮ Non-submodular streaming maximization with minimum memory and low adaptive complexity ⋮ Monotone submodular maximization over the bounded integer lattice with cardinality constraints ⋮ Sequence submodular maximization meets streaming ⋮ Online submodular maximization: beating 1/2 made simple ⋮ The submodularity of two-stage stochastic maximum-weight independent set problems ⋮ An adaptive algorithm for maximization of non-submodular function with a matroid constraint ⋮ An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint ⋮ Non-Submodular Maximization with Matroid and Knapsack Constraints ⋮ Tight Approximation for Unconstrained XOS Maximization

This page was built for publication: Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid