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 itemtobin 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 $11/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 3G cellular service provider networks. This problem fits into our framework. Timepermitting, I may describe more results on convergence in a general class of games, including the distributed caching game.
Timepermitting, 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
Time  Title of Talk 
10:0011:45  Approximation Algorithms for Assignment Problems 
13:0014:45  Mechanism and Convergence in Distributed Caching and Assignment Problems 
Information:
Date:  Jan. 5, 2005 
Place:  Niavaran Bldg., Niavaran Square, Tehran, Iran 
