CAREER: Next Generation Online Resource Allocation

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

This Faculty Early Career Development Program (CAREER) grant will contribute to the advancement of national prosperity and economic welfare by supporting research to study new models and algorithms for dynamic allocation of resources. This work will develop novel, practical algorithmic solutions that can accommodate the complex features, objectives, and constraints arising in applications such as shared mobility, battery swapping for electric vehicles and online advertising. The research will (i) systematic algorithmic insights leading to practical implementations and more robust online platforms; (ii) identify and exploit connections between online resource allocation problems and other areas such as queueing theory, and (iii) enable discovery of new methods for analyzing online algorithms. The accompanying educational plan aims to broaden STEM interest and to provide opportunities for underrepresented communities by training community college instructors on topics related to online resource allocation and operations engineering and collaboratively developing interactive learning modules for community college courses. The research supported by this award will formulate the next generation of models for modern online resource allocation environments and design intuitive algorithms for their solution, emphasizing scalability to large problem instances and the best possible theoretical performance guarantees. This will be accomplished by identifying general structural properties that lead to algorithms that are broadly applicable and robust to changing environments. A major technical emphasis will be on developing methods to analyze adaptive online algorithms that can react to realization of stochastic uncertainties in the problem instance. Adaptive algorithms typically have the best practical performance, but their theoretical analysis is challenging and poorly understood except in some specific settings. Results will include worst case performance bounds and numerical experiments comparing the proposed algorithms with state-of-the-art approaches. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.