A unifying look at sequence submodularity

Several real-world problems in engineering and applied science require the selection of sequences that maximize a given reward function. Optimizing over sequences as opposed to sets requires exploring an exponentially larger search space and can become prohibitive in most cases of practical interest. However, if the objective function is submodular (intuitively, it exhibits a diminishing return property), the optimization problem becomes more manageable. Recently, there has been increasing interest in sequence submodularity in connection with applications such as recommender systems and online ad allocation. However, mostly ad hoc models and solutions have emerged within these applicative contexts. In consequence, the field appears fragmented and lacks coherence. In this paper, we offer a unified view of sequence submodularity and provide a generalized greedy algorithm that enjoys strong theoretical guarantees. We show how our approach naturally captures several application domains, and our algorithm encompasses existing methods, improving over them.

Authors

• Sara Bernardini
• Fabio Fagnani
• Chiara Piacentini

Keywords

• Submodularity
• Sequence submodularity
• Greedy algorithms
• Suboptimal algorithms
• Detection problems
• Search-and-tracking
• Environmental monitoring
• Scheduling
• Recommender systems