Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Probabilistic Analysis of the Simpler Method and Polytope Diameter

Hausdorff Center for Mathematics via YouTube

Overview

Explore a comprehensive lecture on the probabilistic analysis of the simplex method and polytope diameter. Delve into the progress made in understanding the shadow vertex simplex method across three settings: smoothed polytopes, well-conditioned polytopes, and random polytopes with constraints drawn uniformly from the sphere. Examine improvements and simplifications in the complexity analysis of solving smoothed linear programs, and investigate the challenging question of polytope diameter. Learn how randomly chosen shadow paths yield the best known diameter bounds for well-conditioned polytopes and nearly tight diameter bounds for random spherical polytopes. Discover open problems in the field, including quantifying the effectiveness of the simplex method in re-optimizing after adding constraints and exploring the potential of smoothed analysis to explain low iteration counts in interior point methods for solving linear programs.

Syllabus

Introduction
Simplex method
Shadow vertex rule
Why use simplex
Shadow vertex method
Smooth analysis
WhyLinear programming
Results
Key quantity
Shadow bounds
Solution
Questions
Polyhedral duality
Bounds
Perimeter
Polytope diameter
Wide polyhedra
Shadow vertex
Shadow simplex paths
Asymptotic diameter
Summary

Taught by

Hausdorff Center for Mathematics

Reviews

Start your review of Probabilistic Analysis of the Simpler Method and Polytope Diameter

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.