arXiv preprint ·
Mean-only Prophet Inequalities
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study mean-based algorithms for single-choice prophet inequalities: the algorithm knows the number of variables and the mean of their maximum, but not their distributions. For arbitrary independent variables in a fixed order, we can already achieve the optimal $1/2$ competitive ratio using only this mean. For i.i.d. variables and prophet secretary, however, we previously knew only a $1-1/e$ guarantee, which is far away from the ratios with full distribution information. We improve the guarantees in both settings using a simple and natural algorithm: we fix a continuous decreasing threshold function that depends only on the mean and accept the first variable exceeding its threshold. For i.i.d. variables, we prove a $0.7419$ competitive ratio. For the prophet secretary, we prove a $0.6902$ competitive ratio.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Near-Linear Time Maximum Clique in Circular Arc Graphs
No Escape from the Quadratic Barrier: Adaptive Attacks on Linear $\ell_2$ Sketches
Computing faster with a full memory: Catalytic algorithms break time-space lower bounds
Approximating Independent Sets Using Additive Combinatorics
Tree Plurality Veto: Voting in Few Rounds with Efficient Communication and Low Metric Distortion
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.