Technion 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 Abstract: 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 <http://iew3.technion.ac.il/Labs/Seminar/seminar.php?7> ____________________________________________________________________________ Or-seminar mailing list <Or-seminar@iemm1.technion.ac.il> <http://iemm1.technion.ac.il/mailman/listinfo/or-seminar> --------------------------------------------------------- Technion Math. Net (TECHMATH) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: <tomerk@.technion.ac.il>