  We study the problem of online resource allocation, where multiple customers
arrive sequentially and the seller must irrevocably allocate resources to each
incoming customer while also facing a procurement cost for the total
allocation. Assuming resource procurement follows an a priori known marginally
increasing cost function, the objective is to maximize the reward obtained from
fulfilling the customers' requests sans the cumulative procurement cost. We
analyze the competitive ratio of a primal-dual algorithm in this setting, and
develop an optimization framework for synthesizing a surrogate function for the
procurement cost function to be used by the algorithm, in order to improve the
competitive ratio of the primal-dual algorithm. Our first design method focuses
on polynomial procurement cost functions and uses the optimal surrogate
function to provide a more refined bound than the state of the art. Our second
design method uses quasiconvex optimization to find optimal design parameters
for a general class of procurement cost functions. Numerical examples are used
to illustrate the design techniques. We conclude by extending the analysis to
devise a posted pricing mechanism in which the algorithm does not require the
customers' preferences to be revealed.
