Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem.

Anupam Gupta, Amit Kumar, Martin Pl, Tim Roughgarden

Browse the full FOCS paper archive.