- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Improved Algorithms for MST and Metric-TSP Interdiction
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Improved Algorithms for MST and Metric-TSP Interdiction Swamy, Chaitanya
Description
Interdiction problems investigate the sensitivity of an underlying optimization problem with respect to removal of a limited set of underlying elements in order to identify vulnerable spots for possible reinforcement or disruption. We consider the MST-interdiction problem: given a multigraph G with weights and interdiction costs on the edges, and an interdiction budget B, find a set R of edges of total interdiction cost at most B so as to maximize the weight of an MST of G-R. Our main result is a 4-approximation algorithm for this problem. This improves upon the previous-best 14-approximation due to Zenklusen, and notably, our analysis is also significantly simpler and cleaner. Whereas Zenklusen uses a greedy algorithm with an involved analysis to extract a good interdiction set from an over-budget set, we utilize a generalization of knapsack called the tree knapsack problem that nicely captures the key combinatorial aspects of this "extraction problem." We prove a simple, yet strong, LP-relative approximation bound for tree knapsack, which leads to our improved guarantees for MST interdiction. Our algorithm and analysis are nearly tight, as we show that one cannot achieve an approximation ratio better than 3 relative to the upper bound used in our (and the prior) analysis. Our guarantee for MST-interdiction yields an 8-approximation for metric-TSP interdiction. We also show that the maximum-spanning-tree interdiction problem is at least as hard to approximate as the minimization version of densest-k-subgraph. This is joint work with Andre Linhares.
Item Metadata
| Title |
Improved Algorithms for MST and Metric-TSP Interdiction
|
| Creator | |
| Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
| Date Issued |
2017-11-13T10:30
|
| Description |
Interdiction problems investigate the sensitivity of an underlying optimization problem with respect to removal of a limited set of underlying elements in order to identify vulnerable spots for possible reinforcement or disruption. We consider the MST-interdiction problem: given a multigraph G with weights and interdiction costs on the edges, and an interdiction budget B, find a set R of edges of total interdiction cost at most B so as to maximize the weight of an MST of G-R.
Our main result is a 4-approximation algorithm for this problem. This improves upon the previous-best 14-approximation due to Zenklusen, and notably, our analysis is also significantly simpler and cleaner. Whereas Zenklusen uses a greedy algorithm with an involved analysis to extract a good interdiction set from an over-budget set, we utilize a generalization of knapsack called the tree knapsack problem that nicely captures the key combinatorial aspects of this "extraction problem." We prove a simple, yet strong, LP-relative approximation bound for tree knapsack, which leads to our improved guarantees for MST interdiction. Our algorithm and analysis are nearly tight, as we show that one cannot achieve an approximation ratio better than 3 relative to the upper bound used in our (and the prior) analysis. Our guarantee for MST-interdiction yields an 8-approximation for metric-TSP interdiction. We also show that the maximum-spanning-tree interdiction problem is at least as hard to approximate as the minimization version of densest-k-subgraph.
This is joint work with Andre Linhares.
|
| Extent |
32 minutes
|
| Subject | |
| Type | |
| File Format |
video/mp4
|
| Language |
eng
|
| Notes |
Author affiliation: University of Waterloo
|
| Series | |
| Date Available |
2018-05-13
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
| DOI |
10.14288/1.0366261
|
| URI | |
| Affiliation | |
| Peer Review Status |
Unreviewed
|
| Scholarly Level |
Faculty
|
| Rights URI | |
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International