Max Entropy Trees in Approximation Algorithms

Max Entropy Trees in Approximation Algorithms (via Zoom)

Abstract: Max entropy trees were first studied in the context of approximation algorithms about ten years ago. However, many of their magical properties are still being investigated. In this talk I will discuss new (and old) properties of these trees as well as show two applications of their use in rounding solutions to linear programs. The first is a slightly improved approximation algorithm for the traveling salesperson problem (TSP), and the second is an approximation algorithm for the k-edge-connected multi-subgraph problem (k-ECSM) whose approximation ratio goes to 1 as k goes to infinity. I will discuss joint works with Anna Karlin, Shayan Oveis Gharan, and Xinzhi Zhang. 

Bio: I'm a third year PhD student at the University of Washington advised by Anna Karlin and Shayan Oveis Gharan.