The talk will focus on the d-dimensional vector bin packing problem. The input for the problem is a set of items, each associated with a d-dimensional weight vector. The objective is to partition the items into a minimal number of bins, such that the total weight of items in a bin is at most one in every dimension. The problem is a basic generalization of the classic Bin Packing problem and has various applications, such as virtual machines assignment in cloud environments.
In the talk, we will show how iterative randomized rounding, a simple and intuitive algorithmic technique, can be used to attain improved approximation for the d-dimensional vector bin packing problem and other related problems. The technique works in iterations, where each iteration solves a configuration LP relaxation for the residual instance (from previous iterations) and samples a small number of configurations based on the solution for the configuration LP. The main challenge in the analysis is to show that the value of the configuration LP decreases over time.