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||Title of Talk|
|10:00-11:45||Approximation Algorithms for Assignment Problems|
|13:00-14:45||Mechanism and Convergence in Distributed Caching and Assignment Problems|
Date:|| Jan. 5, 2005|
|Place: ||Niavaran Bldg., Niavaran Square, Tehran, Iran|