1. A computer-implemented method comprising: collecting data regarding a plurality of requests for resources available from a service provider; sampling, from the plurality of requests, a number of requests less than all of the plurality of requests to simulate random input of requests; applying an online resource allocation algorithm with the sampled requests as stochastic input, the online resource allocation algorithm configured to, for each request, match said request to resources by evaluating a difference between a profit value and cost computed for different allocation options using an objective function that accounts for shadow costs assigned to the resources corresponding to each of the different allocation options, the shadow costs including computed or estimated costs that are assigned on an individual basis to the resources; and determining whether a feasible solution exists to match the sampled requests to the resources based at least in part on the online resource allocation algorithm.