YoVDO

An O(1)-Approximation for Minimum Spanning Tree Interdiction

Offered By: Hausdorff Center for Mathematics via YouTube

Tags

Minimum Spanning Tree (MST) Courses Graph Theory Courses Combinatorial Optimization Courses

Course Description

Overview

Explore an in-depth lecture on minimum spanning tree (MST) interdiction, a complex network optimization problem. Delve into the mathematical foundations and practical applications of interdiction in various contexts, including infection control and infrastructure protection. Learn about the breakthrough O(1)-approximation algorithm that significantly improves upon previous approaches. Examine key concepts such as connectivity interdiction, network interdiction, and mathematical programming techniques. Gain insights into the relationship between MST interdiction and classical graph disconnection problems like the k-cut problem. Follow the high-level approach to solving the maximum component problem and understand the theorem behind the parametric front method. Suitable for those with a strong background in combinatorial optimization and graph theory.

Syllabus

Intro
What is interdiction
Context
Infection Control
Protecting Infrastructure
Connectivity Interdiction
Network Interdiction
General Techniques
Mathematical Program
Maxim SD Flow
Minimum SD Cut
Disclaimer
Nominal
Assumptions
Maximum Component Problem
Recap
Additional Assumptions
HighLevel Approach
Connected Components
Value of an MST
Parametric front
Theorem
Summary


Taught by

Hausdorff Center for Mathematics

Related Courses

Aplicaciones de la teoría de grafos a la vida real
Miríadax
Aplicaciones de la Teoría de Grafos a la vida real
Universitat Politècnica de València via UPV [X]
Introduction to Computational Thinking and Data Science
Massachusetts Institute of Technology via edX
Genome Sequencing (Bioinformatics II)
University of California, San Diego via Coursera
Algorithmic Information Dynamics: From Networks to Cells
Santa Fe Institute via Complexity Explorer