New approximations for monotone submodular maximization with knapsack constraint

Given a monotone submodular set function with a knapsack constraint, its maximization problem has two types of approximation algorithms with running time \(O(n^2)\) $O(n^2)$ and \(O(n^5)\) $O(n^5)$ , respectively. With running time \(O(n^5)\) $O(n^5)$ , the best performance ratio is \(1-1/e\) $1-1/e$ . With running time \(O(n^2)\) $O(n^2)$ , the well-known performance ratio is \((1-1/e)/2\) $(1-1/e)/2$ and an improved one is claimed to be \((1-1/e^2)/2\) $(1-1/e^2)/2$ recently. In this paper, we design an algorithm with running \(O(n^2)\) $O(n^2)$ and performance ratio \(1-1/e^{2/3}\) $1-1/e^{2/3}$ , and an algorithm with running time \(O(n^3)\) $O(n^3)$ and performance ratio 1/2.