A refined analysis of submodular greedy

DOI10.1016/J.ORL.2021.04.006OpenAlexW3159636333MaRDI QIDQ2060587FDOQ2060587

Authors: Ariel Kulik, Roy Schwartz, Hadas Shachnai 

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

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

zbMATH Keywords

approximation algorithmsknapsack constraintsubmodular functions

Mathematics Subject Classification ID

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

Cites Work

• Elements of Information Theory
• A threshold of ln n for approximating set cover
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Comparison theorems for differential equations
• The budgeted maximum coverage problem
• An analysis of approximations for maximizing submodular set functions—I
• Fast algorithms for maximizing submodular functions
• A note on maximizing a submodular set function subject to a knapsack constraint
• The generalized maximum coverage problem
• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem

Cited In (7)

• 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
• \textsc{Greedy+Singleton}: an efficient approximation algorithm for \(k\)-submodular knapsack maximization
• Stochastic analysis of greedy algorithms for the subset sum problem
• On the Optimality of the Backward Greedy Algorithm for the Subset Selection Problem
• An improved analysis of the Greedy+Singleton algorithm for \(k\)-submodular knapsack maximization

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)