Practical budgeted submodular maximization

DOI10.1007/s00453-022-01071-2OpenAlexW3041209271MaRDI QIDQ2701388

Zeev Nutov, Elad Shoham, Moran Feldman

Publication date: 28 April 2023

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

submodular functionknapsack constraintpractical approximation algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Combinatorics in computer science (68R05) Approximation algorithms (68W25) Graph theory (05Cxx)

Related Items (3)

An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm ⋮ Energy-constrained geometric coverage problem

Cites Work

• Unnamed Item
• Unnamed Item
• The generalized maximum coverage problem
• A note on maximizing a submodular set function subject to a knapsack constraint
• The budgeted maximum coverage problem
• Improved Approximations for k-Exchange Systems
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Fast algorithms for maximizing submodular functions
• Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

This page was built for publication: Practical budgeted submodular maximization