Operations Research & Statistics seminar:
Date: January 28, 2013
Speaker: Leah Epstein, University of Haifa
Title: Generalized selfish bin packing
Time and place: 12:30 in Bloomfield-527
In bin packing problems, a set of items of positive sizes that do not exceed
1 are to be packed into a minimum number of subsets, each of total size
at most 1. In bin packing games, each input item has a positive weight
associated with it, and it has a cost for every valid packing of the set of
input items. We study classes of bin packing games where the cost of an
item is the ratio between its weight and the total weight of items packed
with it, i.e., the cost sharing function is linear in the weights of items. The
weights are positive values, where interesting special cases are unit weights,
and weights that are equal to the sizes. In this work, we study the general
case, as well as the case of unit weights. We consider various kinds of pure
Nash equilibria. Seeing such outcomes of bin packing games as local search
approximation algorithms, we study the asymptotic approximation ratio of
each such algorithm (also called "price of anarchy").
Joint work with Gyorgy Dosa.
You can watch the rest of the seminar plan at our web site
Or-seminar mailing list
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from:  <>