3
Thin spanning trees and their algorithmic applications
http://sms.cam.ac.uk/media/2284101
Saberi, A (Stanford University)
Tuesday 12th July 2016  12:00 to 12:30
40
Thin spanning trees and their algorithmic applications
http://sms.cam.ac.uk/media/2284101
http://rss.sms.cam.ac.uk/itunesimage/2285380.jpg
no

Thin spanning trees and their algorithmic applications
ucs_sms_2283481_2284101
http://sms.cam.ac.uk/media/2284101
Thin spanning trees and their algorithmic applications
Saberi, A (Stanford University)
Tuesday 12th July 2016  12:00 to 12:30
Tue, 19 Jul 2016 12:13:33 +0100
Isaac Newton Institute
Saberi, A
7b850fd51a20c9678e6d31f7444ec902
b9317b1aaf744f098950f745e3f57e8d
185f6b5d9e59750eba25bfbaf3f07d15
c6c158be47e1e15a79844b818429e004
Saberi, A (Stanford University)
Tuesday 12th July 2016  12:00 to 12:30
Saberi, A (Stanford University)
Tuesday 12th July 2016  12:00 to 12:30
Cambridge University
1176
http://sms.cam.ac.uk/media/2284101
Thin spanning trees and their algorithmic applications
Saberi, A (Stanford University)
Tuesday 12th July 2016  12:00 to 12:30
Motivated by Jaeger's modular orientation conjecture, Goddyn asked the following question:
A spanning tree of a graph G is called epsilonthin 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)edgeconnected graph has an epsilonthin 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 KadisonSinger problem.
Bio: http://stanford.edu/~saberi/bio.txt
20160719T12:13:33+01:00
1176
2284101
true
16x9
false
no