Before revision:  Our main result is a simple, linear programming based randomized algorithm that, whenever the instance is feasible, leverages assumptions typically met in practice to return an assignment whose: i) expected cost is at most that of an optimal solution, and ii) expected fraction of unassigned requests is at most 1/e.
After revision:  Our main result is a simple, linear programming based randomized algorithm that, whenever the instance is feasible, leverages mild assumptions to return an assignment whose: i) expected cost is at most that of an optimal solution, and ii) expected fraction of unassigned requests is at most 1/e.