  Online social networks have become the medium for efficient viral marketing
exploiting social influence in information diffusion. However, the emerging
application Social Coupon (SC) incorporating social referral into coupons
cannot be efficiently solved by previous researches which do not take into
account the effect of SC allocation. The number of allocated SCs restricts the
number of influenced friends for each user. In the paper, we investigate not
only the seed selection problem but also the effect of SC allocation for
optimizing the redemption rate which represents the efficiency of SC
allocation. Accordingly, we formulate a problem named Seed Selection and SC
allocation for Redemption Maximization (S3CRM) and prove the hardness of S3CRM.
We design an effective algorithm with a performance guarantee, called Seed
Selection and Social Coupon allocation algorithm. For S3CRM, we introduce the
notion of marginal redemption to evaluate the efficiency of investment in seeds
and SCs. Moreover, for a balanced investment, we develop a new graph structure
called guaranteed path, to explore the opportunity to optimize the redemption
rate. Finally, we perform a comprehensive evaluation on our proposed algorithm
with various baselines. The results validate our ideas and show the
effectiveness of the proposed algorithm over baselines.
