Hausdorff Center for Mathematics Courses

LP-Norm Multiway Cut

Explores graph partitioning with lp-norm multiway cut, unifying min-sum and min-max variants. Discusses hardness, integrality gap, and approximation algorithm for this generalized problem.

• YouTube
• 31 minutes
• Self-Paced
• Free Video

Generalized Permutahedra and Optimal Auctions

Explore SIM-bodies as generalized permutahedra, their role in Straight-Jacket Auctions, and the application of computer algebra for determining optimal prices and revenues in auction theory.

• YouTube
• 34 minutes
• Self-Paced
• Free Video

Noriyoshi Sukegawa- On the Diameter of Polyhedra and Related Topics

Explore polyhedra diameter and its impact on simplex method complexity. Overview previous findings, recent results, and open questions in this mathematical field.

• YouTube
• 56 minutes
• Self-Paced
• Free Video

On Circuit Imbalance Measures and Their Role in Circuit Augmentation Algorithms

Explore new combinatorial condition numbers for linear and integer programs, their relation to existing measures, and their impact on circuit diameter bounds and simplex methods.

• YouTube
• 25 minutes
• Self-Paced
• Free Video

Beyond Value Iteration for Parity Games - Strategy Iteration with Universal Trees

Explores strategy iteration framework for parity games using universal trees, aiming to overcome quasi-polynomial barriers and improve upon value iteration algorithms for efficient game solving.

• YouTube
• 28 minutes
• Self-Paced
• Free Video

Binary Scalar Products

Binary scalar products: Proving a conjecture on 2-level polytopes, exploring their unique properties and demonstrating that the product of vertices and facets is bounded by d2^(d+1) for d-dimensional polytopes.

• YouTube
• 23 minutes
• Self-Paced
• Free Video

Marianne Akian- Tropical Linear Regression and Mean Payoff Games or How to Measure the Distance to Equilibria

Explore tropical linear regression, its connection to mean payoff games, and applications in auction theory. Learn about equilibrium prices and quantifying market distances.

• YouTube
• 32 minutes
• Self-Paced
• Free Video

Separation Theorems in Signed Tropical Convexities

Explores separation theorems in signed tropical convexities, comparing TO and TC-convexities. Presents new results on hyperplane separation, characterizes segments and hemi-spaces, and proves equivalence for generic point collections.

• YouTube
• 32 minutes
• Self-Paced
• Free Video

Polyhedral Geometry of Pivot Rules

Explore the geometric perspective on pivot rules in linear programming, connecting polyhedra, simplex methods, and arborescences to gain insights into optimization algorithms.

• YouTube
• 30 minutes
• Self-Paced
• Free Video

Performance of Steepest Descent in 0/1 LPs

Explores steepest descent in 0/1 LPs, proving polynomial-length paths and developing a new pivot rule for the Simplex method. Unifies circuit and edge steps, advancing understanding of combinatorial optimization.

• YouTube
• 25 minutes
• Self-Paced
• Free Video

Introduction to Parameterized Algorithms and Applications

Explore parameterized complexity and its applications in discrete optimization, focusing on LP-guided techniques, Lenstra's algorithm, and structured ILPs using Graver bases.

• YouTube
• 1 hour 6 minutes
• Self-Paced
• Free Video

Approximation Algorithms for Hard Augmentation Problems - Lecture II

Explore advanced approximation algorithms for network design, focusing on connectivity augmentation problems and recent developments in combinatorial optimization techniques.

• YouTube
• 1 hour 20 minutes
• Self-Paced
• Free Video

Michal Pilipczuk: Introduction to Parameterized Algorithms, Lecture II

Explore parameterized complexity, focusing on LP-related methods. Learn branching, color coding, kernelization, and dynamic programming techniques for algorithm design and optimization.

• YouTube
• 1 hour 9 minutes
• Self-Paced
• Free Video

Approximation Algorithms for Hard Augmentation Problems

Explore advanced network design techniques for increasing graph connectivity, focusing on augmentation problems and recent developments in combinatorial optimization.

• YouTube
• 1 hour 12 minutes
• Self-Paced
• Free Video

Introduction to Interior Point Methods for Discrete Optimization, Lecture I

Explore interior point methods for optimization, their recent advancements, and applications in solving various continuous and combinatorial problems efficiently.

• YouTube
• 1 hour 15 minutes
• Self-Paced
• Free Video