Van-Anh Truong joined the Industrial Engineering and Operations Research Department at the Columbia University in 2010. She received a Bachelor’s degree from University of Waterloo in Mathematics in 2002, and a Ph.D. from Cornell University in Operations Research in 2007. Before coming to Columbia, she was a quantitative associate at Credit Suisse, and a quantitative researcher at Google.
She is interested in a broad class of problems that arise in Supply Chain Management, Healthcare, and Business Analytics. These problems address decision making under uncertainty in information-rich and highly dynamic environments. Her recent work focuses on real-time optimization approaches for large e-commerce, healthcare, and service applications.
Her research is supported by an NSF Faculty Early Career Development (CAREER) Award. She is currently an Associate Editor for Operations Research, MSOM, and Naval Research Logistics.
| Name of Speaker | A/P Van-Anh Truong |
| Schedule | Friday 8 October 2021, 10am (Singapore time) |
| Link to Register | https://nus-sg.zoom.us/meeting/register/tZEpde2trzguGdY7aOovoJ5HUtpniis4z_MM |
| Title | Prophet Inequality with Correlated Arrival Probabilities, with Application to Two Sided Matchings |
| Abstract | The classical Prophet Inequality arises from a fundamental problem in optimal-stopping theory. In this problem, a gambler sees a finite sequence of independent, non-negative random variables. If he stops the sequence at any time, he collects a reward equal to the most recent observation. The Prophet Inequality states that, knowing the distribution of each random variable, the gambler can achieve at least half as much reward in expectation, as a prophet who knows the entire sample path of random variables (Krengel and Sucheston 1978). In this paper, we prove a corresponding bound for correlated non-negative random variables. We analyze two methods for proving the bound, a constructive approach, which produces a worst-case instance, and a reductive approach, which characterizes a certain submartingale arising from the reward process of our online algorithm. We apply this new prophet inequality to the design of algorithms for a class of two-sided bipartite matching problems that underlie online task assignment problems. In these problems, demand units of various types arrive randomly and sequentially over time according to some stochastic process. Tasks, or supply units, arrive according to another stochastic process. Each demand unit must be irrevocably matched to a supply unit or rejected. The match earns a reward that depends on the pair. The objective is to maximize the total expected reward over the planning horizon. The problem arises in mobile crowd-sensing and crowd sourcing contexts, where workers and tasks must be matched by a platform according to various criteria. We derive the first online algorithms with worst-case performance guarantees for our class of two-sided bipartite matching problems. |
