Enhanced deterministic approximation algorithm for non-monotone submodular maximization under knapsack constraint with linear query complexity
Author:
- 22 November 2024
- journal article
- research article
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 49 (1) , 1-14
Abstract
No abstract availableKeywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Improved deterministic algorithms for non-monotone submodular maximizationTheoretical Computer Science, 2023
- Improved approximation algorithms for -submodular maximization under a knapsack constraintComputers & Operations Research, 2023
- Streaming Algorithms for Budgeted k-Submodular Maximization Problem2021
- Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution SchemesSIAM Journal on Computing, 2014
- Fast algorithms for maximizing submodular functions2013
- A Unified Continuous Greedy Algorithm for Submodular Maximization2011
- Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms2010
- Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack ConstraintsSIAM Journal on Discrete Mathematics, 2010
- Cost-effective outbreak detection in networks2007
- A note on maximizing a submodular set function subject to a knapsack constraintOperations Research Letters, 2004