Qin, Junjie and Rajagopal, Ram and Vardi, Shai and Wierman, Adam (2018) Convex Prophet Inequalities. ACM SIGMETRICS Performance Evaluation Review, 46 (2). pp. 85-86. ISSN 0163-5999. doi:10.1145/3305218.3305250. https://resolver.caltech.edu/CaltechAUTHORS:20190128-125707935
![]() |
PDF
- Published Version
See Usage Policy. 1MB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190128-125707935
Abstract
We introduce a new class of prophet inequalities-convex prophet inequalities-where a gambler observes a sequence of convex cost functions ci (xi ) and is required to assign some fraction 0 ≤ x_i ≤ 1 to each, such that the sum of assigned values is exactly 1. The goal of the gambler is to minimize the sum of the costs. We provide an optimal algorithm for this problem, a dynamic program, and show that it can be implemented in polynomial time when the cost functions are polynomial. We also precisely characterize the competitive ratio of the optimal algorithm in the case where the gambler has an outside option and there are polynomial costs, showing that it grows as θ(n^(p-1)/ℓ), where n is the number of stages, p is the degree of the polynomial costs and the coefficients of the cost functions are bounded by [ℓ,u].
Item Type: | Article | ||||||
---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||
Additional Information: | © 2018 held by the owner/author(s). | ||||||
Subject Keywords: | Prophet inequality, online algorithms, resource allocation, stochastic control | ||||||
Issue or Number: | 2 | ||||||
DOI: | 10.1145/3305218.3305250 | ||||||
Record Number: | CaltechAUTHORS:20190128-125707935 | ||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20190128-125707935 | ||||||
Official Citation: | Junjie Qin, Ram Rajagopal, Shai Vardi, and Adam Wierman. 2018. Convex Prophet Inequalities: Extended Abstract. In Proceedings of ACM SIGMETRICS 2018 (SIGMETRICS’18). ACM, Irvine, CA, USA, 2 pages; doi: 10.1145/3305218.3305250 | ||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
ID Code: | 92492 | ||||||
Collection: | CaltechAUTHORS | ||||||
Deposited By: | Tony Diaz | ||||||
Deposited On: | 29 Jan 2019 18:00 | ||||||
Last Modified: | 16 Nov 2021 03:50 |
Repository Staff Only: item control page