Doctoral Thesis Oral Defense - Yige Hong
July 20, 2026 10:00AM—12:00PM
Location:
6501 & Zoom
-
Gates and Hillman Centers
Speaker:
YIGE HONG,
Ph.D. Candidate, Computer Science Department, Carnegie Mellon University
https://yigehong.github.io/
Decision making in large stochastic systems is a central and challenging problem across computer systems, machine learning, and operations research. This thesis studies a wide variety of such systems that, despite their diverse problem definitions, share similar underlying structures and admit similar fundamental techniques for performance analysis and policy design. We identify two such structures, each grouping a family of seemingly distinct problems. The two structures share a common spirit: an intractable system can be approximated by a simpler, well-understood one.
The first part studies the weak-coupling structure, where a system can be approximated by a collection of independent, low-dimensional subsystems. We design a control policy on this simple proxy and convert it into a near-optimal policy for the original, coupled system. Applied to stochastic bin packing, restless bandits, and weakly-coupled Markov decision processes (WCMDPs), this yields efficiently computable policies that are provably near-optimal at scale, under substantially weaker and more easily verifiable conditions than were previously required.
The second part studies the one-dimensional structure, where a key quantity of the system can be approximated by a one-dimensional process even when the full state is high- or infinite-dimensional. Applying this idea to multiserver queues, we prove new universal bounds for the G/G/n queue, show that the Gittins policy is near-optimal for G/G/n queues with setup times, and determine the best achievable delay together with a near-optimal policy for the multiserver-job model.
Thesis Committee:
Weina Wang (Chair)
Mor Harchol-Balter
Alan Scheller-Wolf
Jim Dai (Cornell University)
Yudong Chen (University of Wisconsin-Madison)
Qiaomin Xie (University of Wisconsin-Madison)
In-person & Zoom
Contact
Matt Stewart