Leírás
Abstract: A separable assignment problem (SAP) is defined by a set of bins and a set of items to pack in each bin; a value fij for assigning item j to bin i; and a separate packing constraint for each bin – i.e. for bin i, a family of subsets of items that fit in bin i. The goal is to pack items into bins to maximize the aggregate value. Fleischer et. al. proves that given a ß-approximation algorithm for finding the highest value packing of a single bin, there is a polynomial-time LP-rounding based ((1-1/e)ß)-approximation algorithm, and a polynomial-time local search (ß/ß+1 - epsilon)-approximation algorithm, for any epsilon > 0. This gives a tight approximation for all examples of SAP where the single-bin problem admits an approximation scheme, and for other applications like the AdWords assignment problem or the k-median problem with hard capacities. They also show a hardness result, and study a game-theoretic version of the problem.
After the talk, there will be a short virtual meeting with free discussion on any topic.
Please contact Tamás Király (tkiraly[at]cs.elte.hu) for Zoom access if you are not on the mailing list.