Groupe d’études et de recherche en analyse des décisions

Online packing under random arrival times

Lê Nguyên Hoang MIT, États-Unis

In online packing problems, an allocation to any incoming customer must be determined irrevocably and immediately upon the customer's arrival, without knowledge about future customers. Assuming that customers have random arrival times, we propose and analyze three online algorithms that achieve near optimality. Roughly, this means that, even in worst-case instances, the relative optimality gaps of our algorithms go to zero as the instance sizes scale up, in a certain sense.


Entrée gratuite
Bienvenue à tous!