arXiv preprint ·
Online Matching with Arbitrary Stochastic Rewards
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Online matching with stochastic rewards is a generalization of online bipartite matching in which an attempt to match an online arrival to an offline resource may fail with some probability. Each arrival allows at most one attempt and the success probabilities of its edges are revealed when it arrives. Greedy is 0.5-competitive, which is the best possible for deterministic algorithms. While better competitive ratios are known in several special cases, beating 0.5 for arbitrary probabilities has remained open. We show that, against the adaptive offline benchmark and for arbitrary probabilities, a randomized Perturbed Greedy algorithm is at least 0.591-competitive in the unweighted setting and at least 0.531-competitive with vertex weights. The perturbation functions combine Greedy with scaled versions of the classic exponential function.
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
Conditional stopping guarantees for a folded parametrization of reduced Stokes vectors
Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex $(L_0,L_1)$-Smooth Functions
Optimal Annuitization, Consumption, and Investment with Costly Capital Injections
Point interpolation and distributional universality in flow-based generative models
The Staged Pandora's Box: Reservation Indices for Multi-Fidelity Bayesian Optimization
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.