Submodular Maximization with Cardinality Constraints

DOI10.1137/1.9781611973402.106zbMath1423.90212OpenAlexW4251076636MaRDI QIDQ5384068

Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz

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://semanticscholar.org/paper/9b83f9270bbc7596c9cd6f629d6d12ccdaa5e643

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (50)

Streaming Algorithms for Submodular Function Maximization ⋮ A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization ⋮ Structured Sparsity: Discrete and Convex Approaches ⋮ Measured continuous greedy with differential privacy ⋮ Unnamed Item ⋮ Structured Robust Submodular Maximization: Offline and Online Algorithms ⋮ 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 ⋮ A mobile multi-agent sensing problem with submodular functions under a partition matroid ⋮ Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint ⋮ Beyond submodularity: a unified framework of randomized set selection with group fairness constraints ⋮ Analyzing Residual Random Greedy for monotone submodular maximization ⋮ Constrained Submodular Maximization via a Nonsymmetric Technique ⋮ Improved deterministic algorithms for non-monotone submodular maximization ⋮ Unified Greedy Approximability beyond Submodular Maximization ⋮ Improved deterministic algorithms for non-monotone submodular maximization ⋮ Submodular optimization problems and greedy strategies: a survey ⋮ Unified greedy approximability beyond submodular maximization ⋮ Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid ⋮ Group fairness in non-monotone submodular maximization ⋮ On the equivalence of optimal recommendation sets and myopically optimal query sets ⋮ Influence maximization in the presence of vulnerable nodes: a ratio perspective ⋮ A Survey on Double Greedy Algorithms for Maximizing Non-monotone Submodular Functions ⋮ A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem ⋮ The Submodular Secretary Problem Goes Linear ⋮ Online budgeted maximum coverage ⋮ Deterministic approximation algorithm for submodular maximization subject to a matroid constraint ⋮ Explaining anomalies in groups with characterizing subspace rules ⋮ Weakly Submodular Function Maximization Using Local Submodularity Ratio. ⋮ Non-monotone submodular function maximization under \(k\)-system constraint ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Adaptive robust submodular optimization and beyond ⋮ Monotone submodular maximization over the bounded integer lattice with cardinality constraints ⋮ Sequence submodular maximization meets streaming ⋮ Maximizing monotone submodular functions over the integer lattice ⋮ I/O-efficient calculation of \(H\)-group closeness centrality over disk-resident graphs ⋮ Novel algorithms for maximum DS decomposition ⋮ Semi-streaming algorithms for submodular matroid intersection ⋮ A fast double greedy algorithm for non-monotone DR-submodular function maximization ⋮ Guess free maximization of submodular and linear sums ⋮ Online Submodular Maximization with Preemption ⋮ Approximation algorithms for connected maximum cut and related problems ⋮ An almost optimal approximation algorithm for monotone submodular multiple knapsack ⋮ Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms ⋮ Minimizing ratio of monotone non-submodular functions ⋮ Private non-monotone submodular maximization ⋮ Online Contention Resolution Schemes with Applications to Bayesian Selection Problems ⋮ Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online ⋮ An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint

This page was built for publication: Submodular Maximization with Cardinality Constraints