Metraipolis › archive › dc_2575fead500e

Online Matching with Arbitrary Stochastic Rewards — arXiv:2611.03598

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.03598
License (as archived): CC0-1.0
Archived: 2026-11-03T11:32:45.310Z
SHA-256 of the archived text: f42439e4308aece86feda1bae55d97d142c0ee44463098387260b82f5aeb0daf
Stable URL of this page: https://metraipolis.com/documento/dc_2575fead500e

How to cite

Online Matching with Arbitrary Stochastic Rewards — arXiv:2611.03598 — arXiv (en), https://arxiv.org/abs/2611.03598 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2575fead500e (Metraipolis archive dc_2575fead500e, sha256 f42439e4308aece86feda1bae55d97d142c0ee44463098387260b82f5aeb0daf)

BibTeX

@misc{dc2575fead500e,
  title = {Online Matching with Arbitrary Stochastic Rewards — arXiv:2611.03598},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.03598},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2575fead500e; sha256 f42439e4308aece86feda1bae55d97d142c0ee44463098387260b82f5aeb0daf},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03598. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2611.03598 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:04:22.321Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).