Hao-Xin Sang

Beyond a Single Optimal Design: A Dynamical Systems Characterization of Online Allocation with Convex Costs

Using a principled dynamical-systems approach, it is shown that optimal online algorithms arise as solutions of a nonlinear eigenvalue problem: the optimal competitive ratio corresponds to the dominant eigenvalue, and the associated eigenfunction determines the optimal reserve function.