Haifa University - Dept. of CS Theory Seminar

Speaker : Uri Feige, Weizmann.

Title: "Algorithms for allocation problems"

Date: Thursday, Jan. 3.

Place: Haifa U. Education Building, room 570.

Time: 12:15 - 13:30

Abstract:

We study settings in which players have various valuations for certain goods or for bundles of goods. One has to
allocate the goods to the players in a way that maximizes some objective function. In such settings, a certain
linear programming relaxation, known as the configuration LP, provides an upper bound on the value of the
optimal solution. We present two results with respect to the configuration LP.

1. When utility functions are sub-additive and the goal is to maximize total welfare, we show a rounding
technique with approximation ratio 1/2.

2. In the restricted assignment version of the max-min allocation problem, every good has some intrinsic
nonnegative value and every player is interested only in some of the goods. One has to allocate the goods to the
players in a way that maximizes the minimum of the sum of values of goods given to any player. We show
(nonconstructively) that the value of the configuration LP is larger than the optimum value by at most a
constant factor.