Before revision:  we also derive a probabilistic rejection algorithm which is asymptotically optimal as total demandincreases .
After revision:  we also derive a probabilistic rejection algorithm which is asymptotically optimal in the total demand. Depending on the overall scarcity of resources, either our Sampling or Pooling heuristics could be desirable. The most difficult situation for online allocation occurs when the total supply is just enough to serve the total demand. We simulate our algorithms on a public ride-hailing dataset, which both demonstrates the efficacy of our heuristics and validates our managerial insights .