A refined analysis of submodular greedy

DOI10.1016/J.ORL.2021.04.006MaRDI QIDQ2060587zbMATH OpenOpenAlexFDO

Authors Ariel Kulik, Roy Schwartz, Hadas Shachnai

Publication date 13 December 2021

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

Copyright license Creative Commons Attribution 4.0 International

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)

Recommendations

• A tight analysis of the submodular-supermodular procedure
• Submodular optimization problems and greedy strategies: a survey
• On greedy and submodular matrices
• Unified greedy approximability beyond submodular maximization
• scientific article; zbMATH DE number 874703
• New performance guarantees for the greedy maximization of submodular set functions
• scientific article; zbMATH DE number 3922372
• Analyzing Residual Random Greedy for monotone submodular maximization
• Greedy approximations for minimum submodular cover with submodular cost
• Submodular functions: optimization and approximation

Cites work

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

Cited in

(8)

• Energy-constrained geometric coverage problem
• Stochastic analysis of greedy algorithms for the subset sum problem
• Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm
• \textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization
• An improved analysis of the Greedy+Singleton algorithm for \(k\)-submodular knapsack maximization
• A 1/2 approximation algorithm for energy-constrained geometric coverage problem
• Practical budgeted submodular maximization
• On the Optimality of the Backward Greedy Algorithm for the Subset Selection Problem

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

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