document: Optimizing budget allocation among channels and influencers Brands and agencies use marketing as a tool to influence customers . One of the major decisions in a marketing plan deals with the allocation of a given budget among media channels in order to maximize the impact on a set of potential customers . A similar situation occurs in a social network , where a marketing budget needs to be distributed among a set of potential influencers in a way that provides high-impact . We introduce several probabilistic models to capture the above scenarios . The common setting of these models consists of a bipartite graph of source and target nodes . The objective is to allocate a fixed budget among the source nodes to maximize the expected number of influenced target nodes . The concrete way in which source nodes influence target nodes depends on the underlying model . We primarily consider two models : a source-side influence model , in which a source node that is allocated a budget of k makes k independent trials to influence each of its neighboring target nodes , and a target-side influence model , in which a target node becomes influenced according to a specified rule that depends on the overall budget allocated to its neighbors . Our main results are an optimal ( 1-1 \/ e ) - approximation algorithm for the source-side model , and several inapproximability results for the target-side model , establishing that influence maximization in the latter model is provably harder .
doc_bio_tags: O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O