Events Calendar

04 Nov
Event Type

Lectures, Symposia, Etc.

University Unit
Department of Industrial Engineering
Subscribe
Google Calendar iCal Outlook

IE SEMINAR: Rajan Udwani, "Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources"

This is a past event.

Abstract:

We consider the problem of online allocation (matching, budgeted allocations, and assortments) of reusable resources where an adversarial sequence of resource requests is revealed over time and allocated resources are used/rented for a stochastic duration, drawn independently from known resource usage distributions. This problem is a fundamental generalization of well studied models in online resource allocation and assortment optimization. Previously, it was known that the greedy algorithm that simply makes the best decision for each arriving request is 0.5 competitive against clairvoyant benchmark that knows the entire sequence of requests in advance. We give a new algorithm that is (1-1/e) competitive for arbitrary usage distributions and large resource capacities. This is the best possible guarantee for the problem.

Designing the optimal online policy for allocating reusable resources requires a reevaluation of the key trade off between conserving resources for future requests and being greedy. Resources that are currently in use may return "soon" but the time of return and types of future requests are both uncertain. At the heart of our algorithms is a new quantity that factors in the potential of reusability for each resource by (computationally) creating an asymmetry between identical units of the resource. We establish a performance guarantee for our algorithms by constructing a feasible solution to a novel LP free system of constraints. More generally, these ideas lead to a principled approach for integrating stochastic and combinatorial elements (such as reusability, customer choice, and budgeted allocations) in online resource allocation problems.

Joint work with Vineet Goyal and Garud Iyengar.

Bio: 

Rajan Udwani is an Assistant Professor at UC Berkeley Department of IEOR since 2020. His primary research interests are in the areas of optimization under uncertainty and revenue management, with a focus on applications in online platforms. Before UC Berkeley, He received a PhD in Operations Research from Massachusetts Institute of Technology (MIT) in 2018 and then spent a couple of years as a postdoctoral researcher at Columbia University. He has a B.Tech in Electrical Engineering from IIT Bombay.

Dial-In Information

Join Zoom Meeting

https://pitt.zoom.us/j/91914189290

Meeting ID: 919 1418 9290

Thursday, November 4 at 3:30 p.m. to 4:30 p.m.

Virtual Event

IE SEMINAR: Rajan Udwani, "Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources"

Abstract:

We consider the problem of online allocation (matching, budgeted allocations, and assortments) of reusable resources where an adversarial sequence of resource requests is revealed over time and allocated resources are used/rented for a stochastic duration, drawn independently from known resource usage distributions. This problem is a fundamental generalization of well studied models in online resource allocation and assortment optimization. Previously, it was known that the greedy algorithm that simply makes the best decision for each arriving request is 0.5 competitive against clairvoyant benchmark that knows the entire sequence of requests in advance. We give a new algorithm that is (1-1/e) competitive for arbitrary usage distributions and large resource capacities. This is the best possible guarantee for the problem.

Designing the optimal online policy for allocating reusable resources requires a reevaluation of the key trade off between conserving resources for future requests and being greedy. Resources that are currently in use may return "soon" but the time of return and types of future requests are both uncertain. At the heart of our algorithms is a new quantity that factors in the potential of reusability for each resource by (computationally) creating an asymmetry between identical units of the resource. We establish a performance guarantee for our algorithms by constructing a feasible solution to a novel LP free system of constraints. More generally, these ideas lead to a principled approach for integrating stochastic and combinatorial elements (such as reusability, customer choice, and budgeted allocations) in online resource allocation problems.

Joint work with Vineet Goyal and Garud Iyengar.

Bio: 

Rajan Udwani is an Assistant Professor at UC Berkeley Department of IEOR since 2020. His primary research interests are in the areas of optimization under uncertainty and revenue management, with a focus on applications in online platforms. Before UC Berkeley, He received a PhD in Operations Research from Massachusetts Institute of Technology (MIT) in 2018 and then spent a couple of years as a postdoctoral researcher at Columbia University. He has a B.Tech in Electrical Engineering from IIT Bombay.

Dial-In Information

Join Zoom Meeting

https://pitt.zoom.us/j/91914189290

Meeting ID: 919 1418 9290

Thursday, November 4 at 3:30 p.m. to 4:30 p.m.

Virtual Event

Powered by the Localist Community Events Calendar ©