Practical budgeted submodular maximization

DOI10.1007/S00453-022-01071-2MaRDI QIDQ2701388zbMATH OpenOpenAlexFDO

Authors Moran Feldman, Zeev Nutov, Elad Shoham

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

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

Recommendations

• Generalized budgeted submodular set function maximization
• Fast algorithms for maximizing submodular functions
• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• A refined analysis of submodular greedy
• Submodular maximization with cardinality constraints

Cites work

• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• A \(\frac{(k+3)}{2}\)-approximation algorithm for monotone submodular \(k\)-set packing and general \(k\)-exchange systems
• A note on maximizing a submodular set function subject to a knapsack constraint
• An analysis of approximations for maximizing submodular set functions—I
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Distributed submodular maximization
• Fast algorithms for maximizing submodular functions
• Improved approximations for k-exchange systems (extended abstract)
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• Maximizing a monotone submodular function subject to a matroid constraint
• Monotone submodular maximization over a matroid via non-oblivious local search
• Submodular maximization over multiple matroids via generalized exchange properties
• The budgeted maximum coverage problem
• The generalized maximum coverage problem

Cited in

(9)

• Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm
• Energy-constrained geometric coverage problem
• A 1/2 approximation algorithm for energy-constrained geometric coverage problem
• An exact solver for submodular knapsack problems
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• Budget-constrained profit maximization without non-negative objective assumption in social networks
• Submodular Cost Allocation Problem and Applications
• An improved analysis of the Greedy+Singleton algorithm for \(k\)-submodular knapsack maximization
• A note on fast deterministic algorithms for non-monotone submodular maximization under a knapsack constraint

This page was built for publication: Practical budgeted submodular maximization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2701388)