A refined analysis of submodular greedy

DOI10.1016/j.orl.2021.04.006OpenAlexW3159636333MaRDI QIDQ2060587

Ariel Kulik, Hadas Shachnai, Roy Schwartz

Publication date: 13 December 2021

Published in: Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsknapsack constraintsubmodular functions

Mathematics Subject Classification ID

Numerical analysis (65-XX) Operations research, mathematical programming (90-XX)

Related Items (3)

Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm ⋮ Energy-constrained geometric coverage problem ⋮ \textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization

Cites Work

• The generalized maximum coverage problem
• Comparison theorems for differential equations
• A note on maximizing a submodular set function subject to a knapsack constraint
• The budgeted maximum coverage problem
• A threshold of ln n for approximating set cover
• 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
• Fast algorithms for maximizing submodular functions
• Elements of Information Theory
• A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem

This page was built for publication: A refined analysis of submodular greedy