Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Submodular Function Maximization on the Bounded Integer Lattice
verfasst von : Corinna Gottschalk, Britta Peis
Erschienen in: Approximation and Online Algorithms
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We consider the problem of maximizing a submodular function on the bounded integer lattice. As a direct generalization of submodular set functions, \(f: \{0, \ldots , C\}^n \rightarrow \mathbb {R}_+\) is submodular, if \(f(x) + f(y) \ge f(x \wedge y) + f(x \vee y)\) for all \(x,y \in \{0, \ldots , C\}^n\) where \(\wedge \) and \(\vee \) denote element-wise minimum and maximum. The objective is finding a vector x maximizing f(x). In this paper, we present a deterministic \(\frac{1}{3}\)-approximation using a framework inspired by [2]. We also provide an example that shows the analysis is tight and yields additional insight into the possibilities of modifying the algorithm. Moreover, we examine some structural differences to maximization of submodular set functions which make our problem harder to solve.