AMS Weekly Seminar | Jiaming Xu

Location: Shaffer 3

When: March 12th at 1:30 p.m.

Title: Optimality of Random Regular Graphs in Sparse Network Designs

Abstract: Designing sparse networks that remain efficient under demand uncertainty is a central challenge in operations research. This problem arises in settings such as supply–demand allocation, where firms seek the sparsest bipartite network that performs nearly as well as full flexibility, and in middle-mile logistics, where delivery routes must remain effective despite random fluctuations in station demand.

Prior work has established order-wise optimal sparse designs for both bipartite and unipartite networks. In this talk, I show that a simple construction—the random d-regular graph—achieves the sharp theoretical limit: its average degree matches the minimum possible degree required to attain a given performance loss under uncertainty. This optimality holds in both bipartite and unipartite settings. I will discuss the intuition behind this result, outline the key ideas in the analysis, and present numerical experiments complementing the theory. Our results point to a clear design principle for sparse flexibility networks: enforcing degree regularity while keeping correlations low can achieve optimal performance under uncertainty.

Zoom link: https://wse.zoom.us/j/92366532431