Tong Zhang, G.H. Golub, et al.
Linear Algebra and Its Applications
A note on maximizing a submodular set function subject to a knapsack constraint was presented. An (1-e-1)-approximation algorithm for maximizing a nondecreasing submodular set function was obtained. This algorithm required O(n5) function value computations. The algorithm enumerated all feasible solutions of cardinality one or two.
Tong Zhang, G.H. Golub, et al.
Linear Algebra and Its Applications
Salvatore Certo, Anh Pham, et al.
Quantum Machine Intelligence
Shu Tezuka
WSC 1991
Nimrod Megiddo
Journal of Symbolic Computation