BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//hacksw/handcal//NONSGML v1.0//EN
BEGIN:VEVENT
UID:node-11566@prod.cs.cornell.edu
DTSTAMP:20210405T200000Z
DTSTART:20210405T200000Z
DTEND:20210405T210000Z
SUMMARY:Max Entropy Trees in Approximation Algorithms
DESCRIPTION:Nathan Klein, University of Washington. 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.https://prod.cs.cornell.edu/content/max-entropy-trees-approximation-algorithms
LOCATION:Streaming via Zoom
END:VEVENT
END:VCALENDAR