Unconstrained submodular maximization with modular costs: Tight approximation and application to profit Maximization

Tianyuan Jin, Yu Yang, Renchi Yang, Jieming Shi*, Keke Huang, Xiaokui Xiao

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

12 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)1756-1768
Number of pages13
JournalProceedings of the VLDB Endowment
Volume14
Issue number10
DOIs
Publication statusPublished - Aug 2021
Event47th International Conference on Very Large Data Bases, VLDB 2021 - Virtual, Online
Duration: 16 Aug 202120 Aug 2021

Scopus Subject Areas

  • Computer Science (miscellaneous)
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Unconstrained submodular maximization with modular costs: Tight approximation and application to profit Maximization'. Together they form a unique fingerprint.

Cite this