.png){kind=icon}
.png){kind=icon}
Return
Online generalized assignment problem with historical information
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2022.106047.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Online generalized assignment problem
Online packing problem
Historical information
Random order model
Competitive analysis
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W
View more organizations