Deeparnab Chakrabarty: Provable Submodular Function Minimization via Fujishige Wolfe Algorithm

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


Duration: 3:02
666 views
8

The Fujishige-Wolfe heuristic is empirically one of the fastest algorithms for Submodular Function Minimization and is based upon Wolfe's algorithm to find the nearest point on a polytope to the origin. There was no theoretical guarantees known for the same. In this work we give a convergence analysis for Wolfe's algorithm which implies a pseudo-polynomial running time for the Fujishige Wolfe algorithm.



Other Videos By Microsoft Research


2016-08-09GNM2013: Learning Equilibria of Games via Payoff Queries
2016-08-09Proving That Programs Eventually Do Something Good
2016-08-09Strategic Thinking for Researchers
2016-08-09Data Structures for Efficient Inference and Optimization in Expressive Continuous Domains
2016-08-09Towards A Holistic Approach to Performance Portability for Heterogeneous Systems
2016-08-09Modular reasoning for modular concurrency
2016-08-09Building Better Questionnaires with Probabilistic Modelling
2016-08-08FlashBack: Immersive Virtual Reality on Mobile Devices via Rendering Memoization
2016-08-08SwimTrain: Never swim alone with this cooperative “exergame” for group fitness
2016-08-08Demo of Open Test Platform for LTE/LTE-U
2016-08-08Deeparnab Chakrabarty: Provable Submodular Function Minimization via Fujishige Wolfe Algorithm
2016-08-08Memristors: The Future of Computer Memory and Neuromorphic Circuits?
2016-08-08Number theoretic methods in quantum compiling
2016-08-08Machine Learning Day 2013 - Afternoon Sessions
2016-08-08Discovering the Structure of Visual Categories from Weak Annotations
2016-08-08The Importance of the Center for Computational Thinking
2016-08-08Specification and Verification in Introductory Computer Science
2016-08-08Programming Approximate Systems
2016-08-08Typed functional probabilistic programming: ready for practical use?
2016-08-08eScience in the Medical Domain
2016-08-08Tutorial 2 - Kinect for Windows in Science Applications


Tags:
microsoft research