Techniques for combinatorial optimization: Spectral Graph Theory and Semidefinite Programming

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=ADwygfTLR5g


Duration: 52:01
2,211 views
21

The talk focuses on expander graphs in conjunction with the combined use of SDPs and eigenvalue techniques for approximating optimal solutions to combinatorial optimization problems. In the first part of the talk I will explain how to construct cost-effective, expanding networks by using local sparsifiers of graphs that emerge as a solution to a semidefinite program. In the second part of the talk I will show that the Unique Games Conjecture is false when the underlying constraint graph is a (spectral) expander. Namely, I will present a polynomial-time algorithm for Unique Games on expanding instances that finds a good assignment when there exists one.



Other Videos By Microsoft Research


2016-09-06Remix: Making Art and Commerce Thrive in the Hybrid Economy
2016-09-06From Disasters to WoW: Enabling Knowledge Networks in the 21st century
2016-09-06Panta Rhei: Database Evolution
2016-09-06From Company Man, Family Dinners & Affluence to Home Office, Blackberry Moms and Economic Anxiety
2016-09-06Iterative Methods in Combinatorial Optimization
2016-09-06Inventing the Future: Humanity's Future in Space
2016-09-06Mixing in Time and Space
2016-09-06Abstraction-Guided Hybrid Symbolic Execution for Testing Concurrent Systems
2016-09-06The Church-Turing Thesis: Story and Recent Progress
2016-09-06Investigating the Fundamental Network Burden of Distributed Cooperation
2016-09-06Techniques for combinatorial optimization: Spectral Graph Theory and Semidefinite Programming
2016-09-06Visual Search for an Object in a 3D Environment using a Mobile Robot
2016-09-06Deterministic Parallel Java: Towards Deterministic-by-default Parallel Programming
2016-09-06A Calculus of Atomic Actions
2016-09-06The Edge of Medicine: The Technology that will Change Our Lives
2016-09-06Approximating the optimum: Efficient algorithms and their limits
2016-09-06Modeling and Enacting Electronic Contracts
2016-09-06eScience: Closing Keynote - eScience and the Fourth Paradigm: Supporting Data-centric Science
2016-09-06eScience: Plenary, Keynote - Digital Repositories, Archives and Infrastructures
2016-09-06eScience: Closing Keynote - Distributed and Parallel Programming Environments and their Performance
2016-09-06eScience: Birds of a Feather Session - eScience Inspired Education


Tags:
microsoft research