Dung T.K. Ha

Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint

This work, for the first time, introduces two constant factor approximation algorithms with linear query complexity for non-monotone submodular maximization over a ground set of size n subject to a knapsack constraint, DLA and RLA. DLA is a deterministic algorithm that provides an approximation fac…