A unifying look at sequence submodularity

Sara Bernardini

doi:10.1016/j.artint.2021.103486

Return

A unifying look at sequence submodularity

2021-08-01

Sara Bernardini *

Fabio Fagnani

Chiara Piacentini

DOI：10.1016/j.artint.2021.103486

Original

Save

View PDF

Abstract

En 中文

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. (C) 2021 The Authors. Published by Elsevier B.V.

Keywords:

Submodularity

Sequence submodularity

Greedy algorithms

Suboptimal algorithms

Detection problems

Search-and-tracking

Environmental monitoring

Scheduling

Recommender systems

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.