ICS Theory Group

ICS 269, Winter 2006: Theory Seminar

Mar 17, 2006, in CS 253

Tight Approximation Algorithms for Maximum General Assignment Problems

Authored by: Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, and Maxim Sviridenko

Presented by Matt Nguyen


The authors show that for any separable assignment problem (SAP), if there exists an B-approximation algorithm for solving the single bin case, then there is an LP-based algorithm that yields an (1-1/e - ε)-approximation and a local search algorithm with a (1/2-ε)-approximation. A SAP is defined as follows: Given a set of bins and items to pack into bins, a value f_ij for assigning item j to bin i, and a separate packing constraint on each bin (defined by a set of subsets of items that fit into bin i), find the packing that maximizes the aggregate value.