Continuous Profit Maximization: A Study of Unconstrained Dr-submodular
  Maximization
  Profit maximization (PM) is to select a subset of users as seeds for viral
marketing in online social networks, which balances between the cost and the
profit from influence spread. We extend PM to that under the general marketing
strategy, and form continuous profit maximization (CPM-MS) problem, whose
domain is on integer lattices. The objective function of our CPM-MS is
dr-submodular, but non-monotone. It is a typical case of unconstrained
dr-submodular maximization (UDSM) problem, and take it as a starting point, we
study UDSM systematically in this paper, which is very different from those
existing researcher. First, we introduce the lattice-based double greedy
algorithm, which can obtain a constant approximation guarantee. However, there
is a strict and unrealistic condition that requiring the objective value is
non-negative on the whole domain, or else no theoretical bounds. Thus, we
propose a technique, called lattice-based iterative pruning. It can shrink the
search space effectively, thereby greatly increasing the possibility of
satisfying the non-negative objective function on this smaller domain without
losing approximation ratio. Then, to overcome the difficulty to estimate the
objective value of CPM-MS, we adopt reverse sampling strategies, and combine it
with lattice-based double greedy, including pruning, without losing its
performance but reducing its running time. The entire process can be considered
as a general framework to solve the UDSM problem, especially for applying to
social networks. Finally, we conduct experiments on several real datasets to
evaluate the effectiveness and efficiency of our proposed algorithms.
