Abstract

We give new centralized and distributed approximation algorithms for separable assignment packing problems. A separable assignment packing problem consists of a set of bins and a set of items. It includes a separable, nondecreasing objective function over the item-to-bin assignments and separable sets of packing constraints, one set per bin. For example, each item has a profit and a size for each bin, and each bin has a capacity constraint. The goal is to find an assignment of items to bins that maximizes the objective function. I will describe a $1-1/e$-approximation for these problems based on rounding the solution to a linear program. Then, I will mention a combinatorial, local search approximation algorithm with the guarantee of 1/2. I will mention how to generalize this algorithm for facility location problems with knapsack constraints. Finally, I will describe decentralized mechanisms with the price of anarchy equal to 1/2 and study the convergence in these games. Our investigation of this problem is motivated by the distributed caching problem for content distribution in 3-G cellular service provider networks. This problem fits into our framework. Time-permitting, I may describe more results on convergence in a general class of games, including the distributed caching game. Time-permitting, I will talk about convergence in this game and some related games and show recent progress in the speed of convergence in competitive games.



Time Table