Главная
Study mode:
on
1
Intro
2
What is interdiction
3
Context
4
Infection Control
5
Protecting Infrastructure
6
Connectivity Interdiction
7
Network Interdiction
8
General Techniques
9
Mathematical Program
10
Maxim SD Flow
11
Minimum SD Cut
12
Disclaimer
13
Nominal
14
Assumptions
15
Maximum Component Problem
16
Recap
17
Additional Assumptions
18
HighLevel Approach
19
Connected Components
20
Value of an MST
21
Parametric front
22
Theorem
23
Summary
Description:
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.

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

Hausdorff Center for Mathematics
Add to list