Maximizing Profit with Convex Costs in the Random-order Model

Anupam Gupta, Ruta Mehta, Marco Molinaro

Suppose a set of requests arrives online: each request gives some value $v_i$ if accepted, but requires using some amount of each of $d$ resources. Our cost is a convex function of…