Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/95610
Title: | Unconstrained submodular maximization with modular costs : tight approximation and application to profit maximization | Authors: | Jin, T Yang, Y Yang, R Shi, J Huang, K Xiao, X |
Issue Date: | Jun-2021 | Source: | Proceedings of the VLDB Endowment, June 2021, v. 14, no. 10, p. 1756-1768 | Abstract: | Given a set V, the problem of unconstrained submodular maximization with modular costs (USM-MC) asks for a subset S ⊆V that maximizes f(S) − c (S), where f is a non-negative, monotone, and submodular function that gauges the utility of S, and c is a nonnegative and modular function that measures the cost of S. This problem finds applications in numerous practical scenarios, such as profit maximization in viral marketing on social media. This paper presents ROI-Greedy, a polynomial time algorithm for USM-MC that returns a solution S satisfying {formula presented} where S∗ is the optimal solution to USM-MC. To our knowledge, ROI-Greedy is the first algorithm that provides such a strong approximation guarantee. In addition, we show that this worst-case guarantee is tight, in the sense that no polynomial time algorithm can ensure {formula presented}, for any ε > 0. Further, we devise a non-trivial extension of ROI-Greedy to solve the profit maximization problem, where the precise value of f(S) for any set S is unknown and can only be approximated via sampling. Extensive experiments on benchmark datasets demonstrate that ROI-Greedy significantly outperforms competing methods in terms of the tradeoff between efficiency and solution quality. | Publisher: | Association for Computing Machinery | Journal: | Proceedings of the VLDB Endowment | ISSN: | 2150-8097 | DOI: | 10.14778/3467861.3467866 | Rights: | Copyright is held by the owner/author(s). Publication rights
licensed to the VLDB Endowment. This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. The following publication Jin, T., Yang, Y., Yang, R., Shi, J., Huang, K., & Xiao, X. (2021). Unconstrained submodular maximization with modular costs: Tight approximation and application to profit maximization. Proceedings of the VLDB Endowment, 14(10), 1756-1768 is available at https://doi.org/10.14778/3467861.3467866 |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
3467861.3467866.pdf | 821.45 kB | Adobe PDF | View/Open |
Page views
94
Last Week
0
0
Last month
Citations as of Oct 13, 2024
Downloads
136
Citations as of Oct 13, 2024
SCOPUSTM
Citations
16
Citations as of Oct 17, 2024
WEB OF SCIENCETM
Citations
12
Citations as of Oct 17, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.