Hausdorff Center for Mathematics Courses

Parameterized Problems Complete for Nondeterministic FPT Time and Logarithmic Space

Exploration of XNLP-complete problems in parameterized complexity, including List Coloring, Scheduling, Bandwidth, and CNF-Satisfiability variants, with implications for W[t]-hardness and long-standing questions.

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

Parametrized Algorithms and Possible Future Directions

Explore current research and future directions in Parameterized Complexity, focusing on algorithmic approaches and potential areas for further investigation.

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

The Approximation Ratio of the k-Opt Heuristic for Euclidean TSP

Explore the k-Opt heuristic's approximation ratio for Euclidean TSP, improving upper bounds and providing new lower bounds for k ≥ 3, applicable to various p-norms.

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

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