Lagrangian Decomposition Algorithm for Allocating Marketing Channels


  • Daisuke Hatano National Institute of Informatics
  • Takuro Fukunaga National Institute of Informatics
  • Takanori Maehara National Institute of Informatics
  • Ken-ichi Kawarabayashi National Institute of Informatics



combinatorial optimization, computational advertisement


In this paper, we formulate a new problem related to the well-known influence maximization in the context of computational advertising. Our new problem considers allocating marketing channels (e.g., TV, newspaper, and websites) to advertisers from the view point of a match maker, which was not taken into account in previous studies on the influence maximization. The objective of the problem is to find an allocation such that each advertiser can influence some given number of customers while the slots of marketing channels are limited. We propose an algorithm based on the Lagrangian decomposition. We empirically show that our algorithm computes better quality solutions than existing algorithms, scales up to graphs of 10M vertices, and performs well particularly in a parallel environment.




How to Cite

Hatano, D., Fukunaga, T., Maehara, T., & Kawarabayashi, K.- ichi. (2015). Lagrangian Decomposition Algorithm for Allocating Marketing Channels. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1).



AAAI Technical Track: Heuristic Search and Optimization