Academic Commons

Theses Doctoral

Online Algorithms for Dynamic Resource Allocation Problems

Wang, Xinshang

Dynamic resource allocation problems are everywhere. Airlines reserve flight seats for those who purchase flight tickets. Healthcare facilities reserve appointment slots for patients who request them. Freight carriers such as motor carriers, railroad companies, and shipping companies pack containers with loads from specific origins to destinations.
We focus on optimizing such allocation problems where resources need to be assigned to customers in real time. These problems are particularly difficult to solve because they depend on random external information that unfolds gradually over time, and the number of potential solutions is overwhelming to search through by conventional methods.
In this dissertation, we propose viable allocation algorithms for industrial use, by fully leveraging data and technology to produce gains in efficiency, productivity, and usability of new systems. The first chapter presents a summary of major methodologies used in modeling and algorithm design, and how the methodologies are driven by the size of accessible data.
Chapters 2 to 5 present genuine research results of resource allocation problems that are based on Wang and Truong (2017); Wang et al. (2015); Stein et al. (2017); Wang et al. (2016). The algorithms and models cover problems in multiple industries, from a small clinic that aims to better utilize its expensive medical devices, to a technology giant that needs a cost-effective, distributed resource-allocation algorithm in order to maintain the relevance of its advertisements to hundreds of millions of consumers.

Files

  • thumnail for Wang_columbia_0054D_14218.pdf Wang_columbia_0054D_14218.pdf application/pdf 983 KB Download File

More About This Work

Academic Units
Industrial Engineering and Operations Research
Thesis Advisors
Truong, Van-Anh
Degree
Ph.D., Columbia University
Published Here
October 3, 2017
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.