Unconstrained submodular maximization with modular costs : Tight approximation and application to profit Maximization
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Related Research Unit(s)
|Journal / Publication||Proceedings of the VLDB Endowment|
|Publication status||Published - Jun 2021|
|Title||47th International Conference on Very Large Data Bases (VLDB 2021)|
|Location||Tivoli Hotel & Congress Center (in-person and virtual)|
|Period||16 - 20 August 2021|
|Link to Scopus||https://www.scopus.com/record/display.uri?eid=2-s2.0-85115441626&origin=recordpage|
This paper presents ROI-Greedy, a polynomial time algorithm for USM-MC that returns a solution S satisfying ƒ(S) - c(S) ≥ ƒ(S*) - c(S*) - In ƒ(S*)⁄c(S*) • c(S*) 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 ƒ(S) - c(S) ≥ (1 + ε) • ⟨ƒ(S*) - c(S*) - In ƒ(S*)⁄c(S*) • c(S*)⟩, for any ε > 0. Further, we devise a non-trivial extension of ROI-Greedy to solve the profit maximization problem, where the precise value of ƒ(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.
Unconstrained submodular maximization with modular costs : Tight approximation and application to profit Maximization. / Jin, Tianyuan; Yang, Yu; Yang, Renchi et al.In: Proceedings of the VLDB Endowment, Vol. 14, No. 10, 06.2021, p. 1756-1768.