Posts

Feb 2025Steiner Networks, or, the Price of Fault Tolerance

Notes on what happens to LP relaxations when connectivity requirements go from uniform to non-uniform, and how Jain's iterative rounding recovers a 2-approximation. From EECS 598 with Euiwoong Lee.