Indexed by:
Abstract:
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.
Keyword:
Reprint Author's Address:
Email:
Source :
OPTIMIZATION LETTERS
ISSN: 1862-4472
Year: 2020
Issue: 5
Volume: 14
Page: 1235-1248
1 . 6 0 0
JCR@2022
ESI Discipline: MATHEMATICS;
ESI HC Threshold:46
Cited Count:
WoS CC Cited Count: 12
SCOPUS Cited Count: 15
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 6
Affiliated Colleges: