Deterministic Algorithms for Submodular Maximization Problems

DOI10.1145/3184990zbMath1454.68170arXiv1508.02157OpenAlexW3160905013WikidataQ129685238 ScholiaQ129685238MaRDI QIDQ4554360

Moran Feldman, Niv Buchbinder

Publication date: 13 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

derandomizationsubmodular function maximizationunconstrained submodular maximization

Mathematics Subject Classification ID

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

Related Items (24)

Two-stage stochastic max-weight independent set problems ⋮ Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes ⋮ The Power of Subsampling in Submodular Maximization ⋮ A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice ⋮ Online risk-averse submodular maximization ⋮ Improved deterministic algorithms for non-monotone submodular maximization ⋮ Improved deterministic algorithms for non-monotone submodular maximization ⋮ A binary search double greedy algorithm for non-monotone DR-submodular maximization ⋮ Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid ⋮ Profit maximization in social networks and non-monotone DR-submodular maximization ⋮ A Survey on Double Greedy Algorithms for Maximizing Non-monotone Submodular Functions ⋮ Stochastic Conditional Gradient++: (Non)Convex Minimization and Continuous Submodular Maximization ⋮ Unnamed Item ⋮ Non-monotone submodular function maximization under \(k\)-system constraint ⋮ Adaptive robust submodular optimization and beyond ⋮ Monotone submodular maximization over the bounded integer lattice with cardinality constraints ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ A fast double greedy algorithm for non-monotone DR-submodular function maximization ⋮ The submodularity of two-stage stochastic maximum-weight independent set problems ⋮ k-Submodular maximization with two kinds of constraints ⋮ Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online ⋮ An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint ⋮ Tight Approximation for Unconstrained XOS Maximization ⋮ An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint

This page was built for publication: Deterministic Algorithms for Submodular Maximization Problems