YoVDO

Aaron Sidford- Introduction to Interior Point Methods for Discrete Optimization, Lecture III

Offered By: Hausdorff Center for Mathematics via YouTube

Tags

Interior-Point Methods Courses Discrete Mathematics Courses Discrete Optimization Courses

Course Description

Overview

Dive into the third lecture of a comprehensive series on interior point methods (IPMs) for discrete optimization. Explore the pivotal role of IPMs in recent algorithmic advances, including their application to maximum flow, bipartite matching, linear programming, and geometric median problems. Learn about the theory behind IPMs and their potential for achieving nearly-linear runtimes in various settings. Gain insights into additional properties, key lemmas, minimum cost flow, weighted log barriers, and the concept of Lewis weight barriers. Understand the importance of leverage scores and root deiteration in the context of IPMs. This rigorous introduction provides a thorough overview of the state-of-the-art in IPM theory and its applications to discrete optimization problems.

Syllabus

Introduction
Overview
Plan
Motivations
Last lecture
Last lecture recap
Outline of lecture
Additional properties
First lemma
Second lemma
Minimum cost flow
Weighted log barrier
Why root deiteration
Leverage scores
Lewis weight barrier


Taught by

Hausdorff Center for Mathematics

Related Courses

Discrete Optimization
University of Melbourne via Coursera
Linear and Discrete Optimization
École Polytechnique Fédérale de Lausanne via Coursera
Modeling Discrete Optimization
University of Melbourne via Coursera
Advanced Modeling for Discrete Optimization
University of Melbourne via Coursera
Advanced Modeling for Discrete Optimization 离散优化建模高阶篇
The Chinese University of Hong Kong via Coursera