Random Order Model (ROM) is a well-studied model in online algorithms. In the setting of online algorithms, the input items arrive in a sequence of steps and, after each step, the algorithm has to take an immediate and irrevocable decision based on the past input. In ROM, an adversary specifies the items, but the order of arrival is drawn uniformly at random. Starting from the prototypical secretary problem, ROM has received a lot of attention in online algorithms. This talk will give a brief survey of the area. Then it will focus on a recent result related to bin packing.
Bin packing is a classical problem in optimization, computer science, and discrete mathematics. Here, a set of items with associated sizes needs to be packed in the minimum number of unit-capacity bins. Best-Fit is one of the most prominent and practically used algorithms for the bin packing problem. Kenyon [SODA ’96] studied online bin packing under random-order arrival, and established an upper bound of 1.5 and a lower bound of 1.08 on the random-order ratio of Best-Fit, and it was conjectured that the true ratio is ≈ 1.15. The conjecture, if true, will also imply that Best-Fit (on randomly permuted input) has the best performance guarantee among all the widely-used simple algorithms for (offline) bin packing. In our recent paper [Hebbar, Khan, Sreenivas; SODA ‘24], we make the first progress towards the conjecture, by showing that Best-Fit achieves a random-order ratio of at most 1.5−ε, for a small constant ε > 0. Furthermore, we establish an improved lower bound of 1.144 on the random-order ratio of Best-Fit, nearly reaching the conjectured ratio.
Zoom link: https://us02web.zoom.us/j/88670406480
Meeting ID: 886 7040 6480
This is part of the Bangalore Probability Seminar Series. For details of past and upcoming seminars kindly see Link