EUVIMEDEUVIMED entdecken
Crossref

Logarithmic Regret in the Dynamic and Stochastic Knapsack Problem with Equal Rewards

Alessandro Arlotto, Xinchang Xie

Stochastic Systems · 2020-06 · 10 (2) · 170-191

DOI: 10.1287/stsy.2019.0055 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Stochastic Systems, 2020-06. Verfasst von Alessandro Arlotto und 1 weiteren Autor:innen. Die Arbeit wurde bisher 12-mal zitiert (Crossref) und nennt 46 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study a dynamic and stochastic knapsack problem in which a decision maker is sequentially presented with items arriving according to a Bernoulli process over n discrete time periods. Items have equal rewards and independent weights that are drawn from a known nonnegative continuous distribution F. The decision maker seeks to maximize the expected total reward of the items that the decision maker includes in the knapsack while satisfying a capacity constraint and while making terminal decisions as soon as each item weight is revealed. Under mild regularity conditions on the weight distribution F, we prove that the regret—the expected difference between the performance of the best sequential algorithm and that of a prophet who sees all of the weights before making any decision—is, at most, logarithmic in n. Our proof is constructive. We devise a reoptimized heuristic that achieves this regret bound.

Zitieren

APA

Arlotto, A., & Xie, X. (2020). Logarithmic Regret in the Dynamic and Stochastic Knapsack Problem with Equal Rewards. Stochastic Systems, 10(2), 170-191. https://doi.org/10.1287/stsy.2019.0055

Vancouver

Arlotto A, Xie X. Logarithmic Regret in the Dynamic and Stochastic Knapsack Problem with Equal Rewards. Stochastic Systems. 2020;10(2):170-191. doi:10.1287/stsy.2019.0055

BibTeX
@article{Arlotto2020,
  author = {Arlotto, Alessandro and Xie, Xinchang},
  title = {Logarithmic Regret in the Dynamic and Stochastic Knapsack Problem with Equal Rewards},
  journal = {Stochastic Systems},
  year = {2020},
  volume = {10},
  number = {2},
  pages = {170--191},
  doi = {10.1287/stsy.2019.0055}
}
Kostenlos starten →