  Influencer marketing has become a thriving industry with a global market
value expected to reach 15 billion dollars by 2022. The advertising problem
that such agencies face is the following: given a monetary budget find a set of
appropriate influencers that can create and publish posts of various types
(e.g. text, image, video) for the promotion of a target product. The campaign's
objective is to maximize across one or multiple online social platforms some
impact metric of interest, e.g. number of impressions, sales (ROI), or audience
reach. In this work, we present an original continuous formulation of the
budgeted influencer marketing problem as a convex program. We further propose
an efficient iterative algorithm based on the Frank-Wolfe method, that
converges to the global optimum and has low computational complexity. We also
suggest a simpler near-optimal rule of thumb, which can perform well in many
practical scenarios. We test our algorithm and the heuristic against several
alternatives from the optimization literature as well as standard seed
selection methods and validate the superior performance of Frank-Wolfe in
execution time and memory, as well as its capability to scale well for problems
with very large number (millions) of social users.
