Maximizing Sequence-Submodular Functions and Its Application to Online Advertising

Saeed Alaei (), Ali Makhdoumi () and Azarakhsh Malekian ()
Additional contact information
Saeed Alaei: Google Research, Mountain View, California 94043
Ali Makhdoumi: Fuqua School of Business, Duke University, Durham, North Carolina 27708
Azarakhsh Malekian: Rotman School of Management, University of Toronto, Toronto, Ontario M5S 3E6, Canada

Management Science, 2021, vol. 67, issue 10, 6030-6054

Abstract: Motivated by applications in online advertising, we consider a class of maximization problems where the objective is a function of the sequence of actions and the running duration of each action. For these problems, we introduce the concepts of sequence-submodularity and sequence-monotonicity , which extend the notions of submodularity and monotonicity from functions defined over sets to functions defined over sequences. We establish that if the objective function is sequence-submodular and sequence-nondecreasing, then there exists a greedy algorithm that achieves 1 − 1 / e of the optimal solution. We apply our algorithm and analysis to two applications in online advertising: online ad allocation and query rewriting. We first show that both problems can be formulated as maximizing nondecreasing sequence-submodular functions. We then apply our framework to these two problems, leading to simple greedy approaches with guaranteed performances. In particular, for the online ad allocation problem, the performance of our algorithm is 1 − 1 / e , which matches the best known existing performance, and for the query rewriting problem, the performance of our algorithm is 1 − 1 / e 1 − 1 / e , which improves on the best known existing performance in the literature.

Keywords: submodular function maximization; sequence submodularity; applications to online advertisement; online ad allocation; query rewriting (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.2020.3820 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:67:y:2021:i:10:p:6030-6054

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().