Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint
SIAM Journal on Discrete Mathematics · 2019-01 · 33 (3) · 1452-1471
DOI: 10.1137/16m1107644 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 13.08.2019. Verfasst von Yuichi Yoshida. Die Arbeit wurde bisher 22-mal zitiert (Crossref) und nennt 18 Literaturangaben. Gefördert von: Exploratory Research for Advanced Technology, Japan Society for the Promotion of Science.
Abstract (Originalsprache)
We consider the problem of maximizing a monotone submodular function under a knapsack constraint. We show that, for any fixed $\epsilon > 0$, there exists a polynomial-time algorithm with an approximation ratio $1-c/e-\epsilon$, where $c \in [0,1]$ is the (total) curvature of the input function. This approximation ratio is tight up to $\epsilon$ for any $c \in [0,1]$. To the best of our knowledge, this is the first result for a knapsack constraint that incorporates the curvature to obtain an approximation ratio better than $1-1/e$, which is tight for general submodular functions. As an application of our result, we present a polynomial-time algorithm for the budget allocation problem with an improved approximation ratio.
Förderung
- Exploratory Research for Advanced Technology
- Japan Society for the Promotion of Science
Zitieren
APA
Yoshida, Y. (2019). Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint. SIAM Journal on Discrete Mathematics, 33(3), 1452-1471. https://doi.org/10.1137/16m1107644
Vancouver
Yoshida Y. Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint. SIAM Journal on Discrete Mathematics. 2019;33(3):1452-1471. doi:10.1137/16m1107644
BibTeX
@article{Yoshida2019,
author = {Yoshida, Yuichi},
title = {Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint},
journal = {SIAM Journal on Discrete Mathematics},
year = {2019},
volume = {33},
number = {3},
pages = {1452--1471},
doi = {10.1137/16m1107644}
}
EUVIMED