Journal
OPTIMIZATION LETTERS
Volume 14, Issue 5, Pages 1235-1248Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s11590-019-01430-z
Keywords
Streaming; Non-submodular; d-Knapsack constraint
Ask authors/readers for more resources
Maximizing constrained submodular functions lies at the core of substantial machine learning and data mining. Specially, the case that the data come in a streaming fashion receives more attention in recent decades. In this work, we study the approximation algorithm for maximizing a non-decreasing set function underd-knapsack constraint. Based on the diminishing-return ratio for set functions, a non-trivial algorithm is devised for maximizing the set function without submodularity. Our results cover some known results and provide an effective method for the maximization on set functions no matter they are submodular or not. We also run the algorithm to handle the application of support selection for sparse linear regression. Numerical results show that the output quality of the algorithm is good.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available