The ACO Seminar (2014–2015)

In this talk, we consider the one-dimensional online bin packing problem. First, we review the results related to the worst-case analysis, average-case analysis, and a few alternative analysis methods. In particular, we talk about recent developments which concern algorithms that provide both average-case and worst-case guarantees. In the second part, We consider the bin packing problem under the advice model where the online constraint is relaxed and algorithms receive partial information about the future requests. Finally, we review two recent applications of the problem for resource allocation in the cloud. The first one concerns a fault-tolerant version of online bin packing which is used for private database cloud services. The second applications concerns strategies for renting servers in the cloud which are used by online gaming companies.