EUVIMEDEUVIMED entdecken
Crossref

Technical Note—Greedy Algorithm for Multiway Matching with Bounded Regret

Varun Gupta

Operations Research · 2024-05 · 72 (3) · 1139-1155

DOI: 10.1287/opre.2022.2400 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Operations Research, 2024-05. Verfasst von Varun Gupta. Die Arbeit wurde bisher 26-mal zitiert (Crossref) und nennt 11 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A Unified View of Online Matching and Resource Allocation Problems Whereas small regret online algorithms for applications as diverse as network revenue management (NRM), assemble-to-order (ATO) systems, and online stochastic bin packing (SBP) are known in the literature, the design of the existing algorithms are tailored to the specific application and often use the strategy of resolving a planning linear program. In the paper “Greedy Algorithm for Multiway Matching with Bounded Regret,” Gupta proposes a unified model for studying such online matching/allocation problems. In the unified model, resources of three types—off-line (e.g., inventory in NRM), online-queueable (e.g., orders or resources in ATO systems), or online-nonqueueable (e.g., requests in NRM, items in SBP)—must be combined to create feasible configurations. Leveraging the unified framework, the author gives one simple greedy algorithm that gives small regret (bounded or logarithmic in time horizon) for these diverse applications under a mild nondegeneracy condition on the off-line planning problem.

Zitieren

APA

Gupta, V. (2024). Technical Note—Greedy Algorithm for Multiway Matching with Bounded Regret. Operations Research, 72(3), 1139-1155. https://doi.org/10.1287/opre.2022.2400

Vancouver

Gupta V. Technical Note—Greedy Algorithm for Multiway Matching with Bounded Regret. Operations Research. 2024;72(3):1139-1155. doi:10.1287/opre.2022.2400

BibTeX
@article{Gupta2024,
  author = {Gupta, Varun},
  title = {Technical Note—Greedy Algorithm for Multiway Matching with Bounded Regret},
  journal = {Operations Research},
  year = {2024},
  volume = {72},
  number = {3},
  pages = {1139--1155},
  doi = {10.1287/opre.2022.2400}
}
Kostenlos starten →