CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department Alumni
Algorithms, Combinatorics and Optimization Seminar
Shahin Kamali
University of Waterloo
Title: Online bin packing problem: alternative analysis methods and new applications

Abstract: 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.

Date: Thursday, March 19, 2015
Time: 3:30 pm
Location: Gates 8102
Submitted by:  Bukh
Note: Please note location.