Papers for

online marketplace managers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Randomized algorithm improves online matching success rates above half

Online Matching with Arbitrary Stochastic Rewards

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.

Mon 2 NovData Structures and Algorithms

The gist

Matching online arrivals with offline resources can fail unpredictably, and past methods could only guarantee about half the matches would succeed. The authors present a randomized technique called Perturbed Greedy that improves this guarantee to about 59% for unweighted cases and 53% when resources have different values. This method mixes traditional greedy matching with carefully adjusted probabilistic choices to get better outcomes. Their result applies broadly to many different success probabilities and outperforms all deterministic approaches.

Open → 2611.03598v1