A Unified Continuous Greedy Algorithm for Submodular Maximization

DOI10.1109/FOCS.2011.46zbMath1292.90248OpenAlexW2045492898MaRDI QIDQ5495032

Joseph (Seffi) Naor, Moran Feldman, Roy Schwartz

Publication date: 30 July 2014

Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2011.46

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Fundamental topics (basic mathematics, methodology; applicable to economics in general) (91B02) Approximation algorithms (68W25)

Related Items

Streaming Algorithms for Submodular Function Maximization ⋮ A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization ⋮ Multi-attribute based influence maximization in social networks: algorithms and analysis ⋮ Maximizing Symmetric Submodular Functions ⋮ Measured continuous greedy with differential privacy ⋮ Max-Cut Under Graph Constraints ⋮ Robust Monotone Submodular Function Maximization ⋮ Submodular Stochastic Probing on Matroids ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions ⋮ Structured Robust Submodular Maximization: Offline and Online Algorithms ⋮ Prophet Matching with General Arrivals ⋮ 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 ⋮ Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint ⋮ A bi-criteria algorithm for online non-monotone maximization problems: DR-submodular+concave ⋮ A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice ⋮ Two-stage submodular maximization under knapsack and matroid constraints ⋮ Constrained Submodular Maximization via a Nonsymmetric Technique ⋮ Submodular Maximization Through the Lens of Linear Programming ⋮ The Frank-Wolfe algorithm: a short introduction ⋮ On maximizing sums of non-monotone submodular and linear functions ⋮ 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 ⋮ A stochastic non-monotone DR-submodular maximization problem over a convex set ⋮ Online non-monotone DR-submodular maximization: 1/4 approximation ratio and sublinear regret ⋮ A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint ⋮ Unnamed Item ⋮ Group fairness in non-monotone submodular maximization ⋮ On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints ⋮ Unnamed Item ⋮ A Survey on Double Greedy Algorithms for Maximizing Non-monotone Submodular Functions ⋮ Submodular Optimization with Contention Resolution Extensions. ⋮ A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem ⋮ Stochastic Conditional Gradient++: (Non)Convex Minimization and Continuous Submodular Maximization ⋮ The Submodular Secretary Problem Goes Linear ⋮ Weakly Submodular Function Maximization Using Local Submodularity Ratio. ⋮ Unnamed Item ⋮ Non-monotone submodular function maximization under \(k\)-system constraint ⋮ Blocking rumor by cut ⋮ Viral marketing of online game by DS decomposition in social networks ⋮ Bulk-robust combinatorial optimization ⋮ Monotone submodular maximization over the bounded integer lattice with cardinality constraints ⋮ Sequence submodular maximization meets streaming ⋮ Approximating graph-constrained max-cut ⋮ Robust monotone submodular function maximization ⋮ Approximating max-cut under graph-MSO constraints ⋮ Constrained submodular maximization via greedy local search ⋮ Online submodular maximization: beating 1/2 made simple ⋮ \(\ell_1\)-sparsity approximation bounds for packing integer programs ⋮ Novel algorithms for maximum DS decomposition ⋮ Guess free maximization of submodular and linear sums ⋮ Online Submodular Maximization with Preemption ⋮ Harnessing the power of deception in attack graph-based security games ⋮ Set function optimization ⋮ Submodular Maximization with Uncertain Knapsack Capacity ⋮ An almost optimal approximation algorithm for monotone submodular multiple knapsack ⋮ Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints ⋮ Nonsubmodular constrained profit maximization from increment perspective ⋮ Private non-monotone submodular maximization ⋮ Online Contention Resolution Schemes with Applications to Bayesian Selection Problems ⋮ An adaptive algorithm for maximization of non-submodular function with a matroid constraint ⋮ Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online ⋮ An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint ⋮ An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint

This page was built for publication: A Unified Continuous Greedy Algorithm for Submodular Maximization