## 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

Abstract:

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.