Back to Search
Start Over
A Refined Analysis of Submodular Greedy
- Source :
- Operations Research Letters
- Publication Year :
- 2021
- Publisher :
- arXiv, 2021.
-
Abstract
- Many algorithms for maximizing a monotone submodular function subject to a knapsack constraint rely on the natural greedy heuristic. We present a novel refined analysis of this greedy heuristic which enables us to: (1) reduce the enumeration in the tight ( 1 − e − 1 ) -approximation of [Sviridenko 04] from subsets of size three to two; (2) present an improved upper bound of 0.42945 for the classic algorithm which returns the better between a single element and the output of the greedy heuristic.
- Subjects :
- FOS: Computer and information sciences
021103 operations research
Computer science
Applied Mathematics
0211 other engineering and technologies
Single element
02 engineering and technology
Management Science and Operations Research
01 natural sciences
Upper and lower bounds
Industrial and Manufacturing Engineering
Submodular set function
Combinatorics
010104 statistics & probability
Monotone polygon
Computer Science - Data Structures and Algorithms
Enumeration
Data Structures and Algorithms (cs.DS)
0101 mathematics
Greedy algorithm
Software
Knapsack constraint
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- Operations Research Letters
- Accession number :
- edsair.doi.dedup.....e1e5df83bdceec8ce6c528b337a3371c
- Full Text :
- https://doi.org/10.48550/arxiv.2102.12879