The ACO Seminar (2014–2015)
Mar. 19, 3:30pm, Gates 8102 (Note unusual location)
Shahin Kamali, University of Waterloo
Online bin packing problem: alternative analysis methods and new applications
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.
Back to the ACO home page