Effective-Resistance-Reducing Flows, Spectrally Thin Trees and Asymmetric TSP

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=g-OJf2r-1UU


Duration: 1:00:24
225 views
3

We show that the integrality gap of the natural LP relaxation of the Asymmetric Traveling Salesman Problem is at most polyloglog(n). In other words, there is a polynomial time algorithm that approximates the value of the optimum tour within a factor of polyloglog(n). To prove this, we show that any k-edge-connected graph (for k=Omega(log(n))) has a polylog(k)/k thin tree. In this talk I will highlight the main ideas of our proof. This is a joint work with Nima Anari.



Other Videos By Microsoft Research


2016-06-21Recent Advances in Deep Learning at Microsoft: A Selected Overview
2016-06-21The Interplay of Social Influence and Own Preference in Social Networks
2016-06-21A Fast Distributed Algorithm for α-Fair Packing Problems
2016-06-21Theory Day Session 3
2016-06-21Provable Submodular Minimization via Wolfe’s Algorithm
2016-06-21A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization
2016-06-21Stochastic Methods for Complex Performance Measures: A Tale of Two Families
2016-06-21Parallel Bayesian Network Structure Learning for Genome-Scale Gene Networks
2016-06-21Empirical Inference for Intelligent Systems
2016-06-21Ordered Stick-breaking Prior for Sequential MCMC Inference of Bayesian Non-Parametric Models
2016-06-21Effective-Resistance-Reducing Flows, Spectrally Thin Trees and Asymmetric TSP
2016-06-21Non-Convex Robust PCA
2016-06-21Communication-Avoiding Algorithms and Fast Matrix Multiplication
2016-06-21The Forza Motorsport 5 Original Soundtrack, An Insider's View
2016-06-21Reasoning about GADT Pattern Matching in Haskell
2016-06-21Non-Convex Robust PCA - Part 2
2016-06-21Modeling, Quantifying, and Limiting Adversary Knowledge
2016-06-21Sampling Techniques for Constraint Satisfaction and Beyond
2016-06-21Cell Classification of FT-IR Spectroscopic Data for Histopathology using Neural Networks
2016-06-21Sequential Equilibrium Distributions in Multi-Stage Games with Infinite Sets of Types and Actions
2016-06-21Randomized Interior Point Methods for Sampling and Optimization


Tags:
microsoft research