TY - JOUR

T1 - Unconstrained submodular maximization with modular costs

T2 - 47th International Conference on Very Large Data Bases, VLDB 2021

AU - Jin, Tianyuan

AU - Yang, Yu

AU - Yang, Renchi

AU - Shi, Jieming

AU - Huang, Keke

AU - Xiao, Xiaokui

N1 - Funding Information:
Xiaokui Xiao is supported by the National University of Singapore under SUG grant R-252-000-686-133. Tianyuan Jin is supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: AISG-PhD/2021-01-004[T]). Yu Yang is supported in part by the Hong Kong Research Grants Council (ECS 21214720) and City University of Hong Kong (Project 9610465). Jieming Shi is supported by the financial support (1-BE3T) of research project (P0033898) from Hong Kong Polytechnic University. The findings herein reflect the work, and are solely the responsibility, of the authors.
Publisher Copyright:
© by the owner/author(s).

PY - 2021/8

Y1 - 2021/8

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85115441626&partnerID=8YFLogxK

U2 - 10.14778/3467861.3467866

DO - 10.14778/3467861.3467866

M3 - Conference article

AN - SCOPUS:85115441626

SN - 2150-8097

VL - 14

SP - 1756

EP - 1768

JO - Proceedings of the VLDB Endowment

JF - Proceedings of the VLDB Endowment

IS - 10

Y2 - 16 August 2021 through 20 August 2021

ER -