Metraipolis › archive › dc_adde183bc944

Online Bipartite Matching with Reusable Capacity under Non-Stationary Rewards — arXiv:2608.18130

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.18130
License (as archived)
CC0-1.0
Archived
2026-10-18T13:53:41.015Z
SHA-256 of the archived text
f8f6f313cb161ead48bbc05dcb0231c71daf3ca293bffad3916449a534f08df5
Stable URL of this page
https://metraipolis.com/documento/dc_adde183bc944

How to cite

Online Bipartite Matching with Reusable Capacity under Non-Stationary Rewards — arXiv:2608.18130 — arXiv (en), https://arxiv.org/abs/2608.18130 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_adde183bc944 (Metraipolis archive dc_adde183bc944, sha256 f8f6f313cb161ead48bbc05dcb0231c71daf3ca293bffad3916449a534f08df5)
BibTeX
@misc{dcadde183bc944,
  title = {Online Bipartite Matching with Reusable Capacity under Non-Stationary Rewards — arXiv:2608.18130},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.18130},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_adde183bc944; sha256 f8f6f313cb161ead48bbc05dcb0231c71daf3ca293bffad3916449a534f08df5},
  year = {2026}
}

Archived text

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

We study online bipartite matching with reusable server capacity and non-stationary rewards. Jobs arrive sequentially, reveal compatible servers, reward rates, and processing durations, and must be accepted or rejected irrevocably. An accepted job occupies one unit of server capacity only during its processing interval, so an assignment may displace an unknown sequence of future jobs. Existing guarantees are typically calibrated by a global reward range, which can become arbitrarily large when rewards drift over a long horizon. We instead impose a locally bounded reward condition: reward rates of jobs that can compete for the same server within a relevant time window differ by at most a factor $\delta$. Under this condition, we develop two BALANCE-type algorithms with time-aware opportunity-cost losses. TS-BAL maximizes cumulative blocking losses over feasible reuse schedules and achieves a competitive ratio of $2\ln(\delta D)+\mathcal O(\ln\ln(\delta\vee D))$. GR-BAL uses a greedy relaxation of this loss and achieves $\ln(\delta D)+\mathcal O(\ln\ln(\delta\vee D))$, matching a lower bound of $\ln(\delta D)$ in the leading term. Numerical experiments demonstrate robust performance under substantial global reward drift and favorable finite-capacity performance.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-20 in cs.LG).
Categorie arXiv: Optimization and Control (math.OC) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2608.18130 — 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-10-18T13:50:58.977Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-08-20?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).