Before revision:  We can relax the feasibility requirement by including a penalty term for unassigned requests, in which case our performance guarantee is with respect to a modified objective function. Our techniques generalize to a class of set-partitioning problems .
After revision:  We can relax the feasibility requirement by considering the penalty version of the problem, in which a penalty is paid for each unassigned request. We find that, whenever a request is repeatedly unassigned after a number of rounds, with high probability it is so in accordance with the sequence of LP solutions and not because of a rounding error. We additionally introduce a deterministic rounding heuristic inspired by our randomized technique. Our computational experiments show that our rounding algorithms achieve a performance similar to that of the ILP at a reduced computation time, far improving on our theoretical guarantee. The reason for this is that, although the assignment problem is hard in theory, the natural LP relaxation tends to be very tight in practice. We conclude with observations and open questions related to this phenomenon .