Group for Research in Decision Analysis

Online packing under random arrival times

Lê Nguyên Hoang MIT, United States

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.

Free entrance.
Welcome to everyone!