Speaker:

Yiding Feng（University of Chicago)

Time:

• 11:00-12:00 (Time in Beijing)
• August 4, 2023 (Friday)

Venue:

518, Research Building 4

Abstract:

The recent large-scale availability of mobility data, which captures individual mobility patterns, poses novel operational problems that are exciting and challenging. Motivated by this, we introduce and study a variant of the (cost-minimization) facility location problem where each individual is endowed with two locations (hereafter, her home and work locations), and the connection cost is the minimum distance between any of her locations and its closest facility. We design a polynomial-time algorithm whose approximation ratio is at most 3.103. We complement this positive result by showing that the proposed algorithm is at least a 3.073-approximation, and there exists no polynomial-time algorithm with an approximation ratio of 2 − ϵ under UG-hardness. We further extend our results and analysis to the model where each individual is endowed with K locations. Finally, we conduct numerical experiments over both synthetic data and US census data (for NYC, greater LA, greater DC, and Research Triangle) and evaluate the performance of our algorithms.

Speaker Bio:

Yiding Feng is a postdoctoral principal researcher at the University of Chicago Booth School of Business. Previously, he worked as a postdoctoral researcher at Microsoft Research New England from 2021 to 2023. He received his Ph.D. from the Department of Computer Science, Northwestern University in 2021. His primary research focuses on theoretical computer science, economics & computation, and operations research.