Thin spanning trees and their algorithmic applications

Add to your list(s) Download to your calendar using vCal

• Amin Saberi (Stanford University)
• Tuesday 12 July 2016, 12:00-12:30
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact info@newton.ac.uk.

SNAW01 - Graph limits and statistics

Motivated by Jaeger's modular orientation conjecture, Goddyn asked the following question: 

A spanning tree of a graph G is called epsilon-thin if it contains at most an epsilon fraction of the edges of each cut in that graph. Is there a function f:(0,1)→ ℤ such that every f(epsilon)-edge-connected graph has an epsilon-thin spanning tree?
 
I will talk about our journey in search of such thin trees, their applications concerning traveling salesman problems, and unexpected connections to graph sparsification and the Kadison-Singer problem.

Bio: saberi/bio.txt" target="_blank" rel="nofollow">http://stanford.edu/saberi/bio.txt

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Featured lists
• INI info aggregator
• Interested Talks
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• rp587

Note that ex-directory lists are not shown.