Generalized budgeted submodular set function maximization

DOI10.1016/j.ic.2021.104741OpenAlexW2886054122MaRDI QIDQ2051778

Francesco Cellinese, Yllka Velaj, Gianpiero Monaco, Gianlorenzo D'Angelo

Publication date: 25 November 2021

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9613/

zbMATH Keywords

approximation algorithmssubmodular set functionbudgeted maximum coverage

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the maximum betweenness improvement problem
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• The generalized maximum coverage problem
• A note on maximizing a submodular set function subject to a knapsack constraint
• The budgeted maximum coverage problem
• Recommending links through influence maximization
• A 6/5-approximation algorithm for the maximum 3-cover problem
• Maximizing Non-monotone Submodular Functions
• A threshold of ln n for approximating set cover
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• An analysis of approximations for maximizing submodular set functions—I
• Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
• Wavelength Management in WDM Rings to Maximize the Number of Connections

This page was built for publication: Generalized budgeted submodular set function maximization