Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint
Open Access
- 7 June 2021
- journal article
- meeting abstracts
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 49 (1), 63-64
- https://doi.org/10.1145/3543516.3453925
Abstract
Monotone submodular maximization with a knapsack constraint is NP-hard. Various approximation algorithms have been devised to address this optimization problem. In this paper, we revisit the widely known modified greedy algorithm. First, we show that this algorithm can achieve an approximation factor of 0.405, which significantly improves the known factors of 0.357 given by Wolsey and (1-1/e)/2-0.316 given by Khuller et al. More importantly, our analysis closes a gap in Khuller et al.'s proof for the extensively mentioned approximation factor of (1-1/√e)≈0.393 in the literature to clarify a long-standing misconception on this issue. Second, we enhance the modified greedy algorithm to derive a data-dependent upper bound on the optimum, which enables us to obtain a data-dependent ratio typically much higher than 0.405 between the solution value of the modified greedy algorithm and the optimum. It can also be used to significantly improve the efficiency of algorithms such as branch and bound.Keywords
Funding Information
- Anhui Initiative in Quantum Information Technologies (AHY150300)
- National Natural Science Foundation of China (61772491, U1709217)
- Singapore Ministry of Education (MOE2019-T1-002-042)
- National Science Foundation Grant (CNS-1951952)
- National Key R&D Program of China (2018AAA0101204)
- Singapore National Research Foundation (NRF-RSS2016-004)
This publication has 10 references indexed in Scilit:
- Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack ConstraintPublished by Association for Computing Machinery (ACM) ,2021
- Trajectory-driven Influential Billboard PlacementPublished by Association for Computing Machinery (ACM) ,2018
- A note on maximizing a submodular set function subject to a knapsack constraintOperations Research Letters, 2004
- Maximizing the spread of influence through a social networkPublished by Association for Computing Machinery (ACM) ,2003
- The budgeted maximum coverage problemInformation Processing Letters, 1999
- A threshold of ln n for approximating set coverJournal of the ACM, 1998
- Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location ProblemsMathematics of Operations Research, 1982
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978
- Best Algorithms for Approximating the Maximum of a Submodular Set FunctionMathematics of Operations Research, 1978
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate AlgorithmsManagement Science, 1977