Recent Developments in Combinatorial Optimization

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


Duration: 40:14
2,244 views
28

In the past several years, there has been a lot of progress on combinatorial optimization. Using techniques in convex optimization, geometry, spectral graph theory and randomization, researchers have developed provably faster algorithms for many classical problems such as linear programming and maximum flow problems. In this talk, I will discuss my work in this area and illustrate it through my recent result on the feasibility problem. Many optimization problems in computer science are shown to be polynomial-time-solvable by reducing it to the feasibility problem and then applying ellipsoid method. However, ellipsoid method is not very efficient. I will present an alternative, the first nearly cubic time algorithm for the feasibility problem. Furthermore, I will discuss how to use this to obtain faster algorithms for submodular minimization, matroid intersection and semidefinite programming.



Other Videos By Microsoft Research


2016-06-13Verasco, a formally verified C static analyzer
2016-06-13Future Microprocessors Driven by Dataflow Principles
2016-06-13Theory and Experiments on the Spontaneous Evolution of Culture
2016-06-13Single-shot error correction with the gauge color code
2016-06-13Robust Spectral Inference for Joint Stochastic Matrix Factorization and Topic Modeling
2016-06-13How Much Information Does a Human Translator Add to the Original and Multi-Source Neural Translation
2016-06-13Opportunities and Challenges in Global Network Cameras
2016-06-13Nature in the City: Changes in Bangalore over Time and Space
2016-06-13Making Small Spaces Feel Large: Practical Illusions in Virtual Reality
2016-06-13Machine Learning as Creative Tool for Designing Real-Time Expressive Interactions
2016-06-13Recent Developments in Combinatorial Optimization
2016-06-13Computational Limits in Statistical Inference: Hidden Cliques and Sum of Squares
2016-06-13Coloring the Universe: An Insider's Look at Making Spectacular Images of Space
2016-06-13Towards Understandable Neural Networks for High Level AI Tasks - Part 6
2016-06-13The 37th UW/MS Symposium in Computational Linguistics
2016-06-13The Linear Algebraic Structure of Word Meanings
2016-06-13Machine Learning Algorithms Workshop
2016-06-13Interactive and Interpretable Machine Learning Models for Human Machine Collaboration
2016-06-13Improving Access to Clinical Data Locked in Narrative Reports: An Informatics Approach
2016-06-13Representation Power of Neural Networks
2016-06-13Green Security Games


Tags:
microsoft research
algorithms
semidefinite programming
program languages and software engineering