Fast algorithms for maximizing submodular functions

DOI10.1137/1.9781611973402.110zbMath1422.68286OpenAlexW4231490457MaRDI QIDQ5384072

Jan Vondrák, Ashwinkumar Badanidiyuru

Publication date: 20 June 2019

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

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (50)

Siting renewable power generation assets with combinatorial optimisation ⋮ Submodular Maximization Subject to a Knapsack Constraint Under Noise Models ⋮ Faster approximation algorithms for maximizing a monotone submodular function subject to a \(b\)-matching constraint ⋮ Streaming Algorithms for Submodular Function Maximization ⋮ An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ Robust Adaptive Submodular Maximization ⋮ Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms ⋮ Structured Robust Submodular Maximization: Offline and Online Algorithms ⋮ The Power of Subsampling in Submodular Maximization ⋮ A Framework for the Secretary Problem on the Intersection of Matroids ⋮ An optimal streaming algorithm for non-submodular functions maximization on the integer lattice ⋮ A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice ⋮ Seeding with Costly Network Information ⋮ Submodular maximization meets streaming: matchings, matroids, and more ⋮ The Frank-Wolfe algorithm: a short introduction ⋮ A single factor approximation ratio algorithm for DR-submodular maximization on integer lattice beyond non-negativity and monotonicity ⋮ Improved deterministic algorithms for non-monotone submodular maximization ⋮ Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity ⋮ Efficient processing of \(k\)-regret minimization queries with theoretical guarantees ⋮ Improved deterministic algorithms for non-monotone submodular maximization ⋮ A note for approximating the submodular cover problem over integer lattice with low adaptive and query complexities ⋮ Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid ⋮ Practical budgeted submodular maximization ⋮ Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time ⋮ Unnamed Item ⋮ Non-submodular streaming maximization with minimum memory and low adaptive complexity ⋮ Monotone submodular maximization over the bounded integer lattice with cardinality constraints ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ Robust monotone submodular function maximization ⋮ Maximizing monotone submodular functions over the integer lattice ⋮ Constrained submodular maximization via greedy local search ⋮ Online submodular maximization: beating 1/2 made simple ⋮ A fast double greedy algorithm for non-monotone DR-submodular function maximization ⋮ Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint ⋮ Guess free maximization of submodular and linear sums ⋮ Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint ⋮ Approximation algorithms for connected maximum cut and related problems ⋮ A refined analysis of submodular greedy ⋮ A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint ⋮ Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint ⋮ Efficient approximation algorithms for maximum coverage with group budget constraints ⋮ Multi-pass streaming algorithms for monotone submodular function maximization ⋮ Better streaming algorithms for the maximum coverage problem ⋮ An adaptive algorithm for maximization of non-submodular function with a matroid constraint ⋮ k-Submodular maximization with two kinds of constraints ⋮ Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online ⋮ Non-Submodular Maximization with Matroid and Knapsack Constraints ⋮ Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model ⋮ Maximum coverage with cluster constraints: an LP-based approximation technique

This page was built for publication: Fast algorithms for maximizing submodular functions