הרצאה פומבית - Online Packing and Covering Problems

Abstract: 

Packing and covering problems model a wide range of problems in combinatorial optimization and operations research. In algorithmic theory, they have been used in many areas including machine scheduling, packet routing, energy minimization, etc.

We focus on the online version of these problems where input arrives on the fly, and the algorithm needs to make irrevocable decisions without knowing the future in advance.  A classic example of a packing problem is the bin packing problem, where we are given a set of items (each of which has some size).  The goal is to pack the items using as few bins as possible, under some constraints on the packed items (i.e., the total size of the items assigned to a bin must be at most the bin’s size).  In the online setting, items arrive on the fly and need to be packed immediately.We give various results for Vector Bin Packing, where each item is described as a $d$-dimensional vector.  A set of vectors can be packed into a single bin if the total size in each dimension of these vectors is at most the bin’s capacity.

A classic example of a covering problem is the online set cover problem, where a set of elements arrive on the fly, and the online algorithm needs to (irrevocably) choose sets to cover the incoming elements.  Each set has some weight, and the goal is to minimize the total weight of the chosen sets.  In this work we extensively expand the model.  We develop a framework that enables us to solve the problem where the goal is to minimize any convex function of the chosen sets instead of just the total weight.

Finally, we give a game theoretical interpretation for some classic online problems, where we view online events as selfish agents and design a dynamic pricing scheme over each agent's possible decisions.

This seminar presents part of the speaker's Ph.D. thesis under the same name, carried out under the supervision of Prof. Yossi Azar.