Online generalized assignment problem with historical information

Haodong Liu, Huili Zhang, Kelin Luo, Yao Xu, Yinfeng Xu, Weitian Tong

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

The rapid development of online platforms has inspired a wide range of applications for timely resources allocations, such as the hotel booking, the cargo logistics, the cloud servers and so on. Motivated by such needs, we study the online versions of the famous generalized assignment problem (GAP) and the packing problem (also known as d-GAP) in the classic random order model, where the online items arrive over time randomly and uniformly and request specific offline resources. Along a recent line of research that uses historical information to improve the performance of online algorithms, we design effective competitive algorithms for both online GAP and d-GAP (d⩾2) with augmentation of historical information. Our algorithms are inspired by Albers et al.’s sequential approach (Albers et al., 2021). If no historical information can be accessed, our algorithm for online GAP reduces to Albers et al.’s algorithm, and our algorithm for online d-GAP (d⩾2) outperforms the current best algorithm (Kesselheim et al., 2018). The practical performance of the proposed algorithms is explored via experiments on both synthetic and real-life datasets. In particular, the positive effect of historical information can be verified by the experiment results.

Original languageEnglish
Article number106047
JournalComputers and Operations Research
Volume149
DOIs
StatePublished - Jan 2023

Scopus Subject Areas

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research

Keywords

  • Competitive analysis
  • Historical information
  • Online generalized assignment problem
  • Online packing problem
  • Random order model

Fingerprint

Dive into the research topics of 'Online generalized assignment problem with historical information'. Together they form a unique fingerprint.

Cite this