Linhares, André ;
Swamy, Chaitanya
Improved Algorithms for MST and MetricTSP Interdiction
Abstract
We consider the MSTinterdiction problem: given a multigraph G = (V, E), edge weights {w_e >= 0}_{e in E}, interdiction costs {c_e >= 0}_{e in E}, and an interdiction budget B >= 0, the goal is to remove a subset R of edges of total interdiction cost at most B so as to maximize the wweight of an MST of GR:=(V,ER).
Our main result is a 4approximation algorithm for this problem. This improves upon the previousbest 14approximation [Zenklusen, FOCS 2015]. Notably, our analysis is also significantly simpler and cleaner than the one in [Zenklusen, FOCS 2015]. Whereas Zenklusen uses a greedy algorithm with an involved analysis to extract a good interdiction set from an overbudget 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, LPrelative 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 analysis (and the one in [Zenklusen, FOCS 2015]).
Our guarantee for MSTinterdiction yields an 8approximation for metricTSP interdiction (improving over the 28approximation in [Zenklusen, FOCS 2015]). We also show that maximumspanningtree interdiction is at least as hard to approximate as the minimization version of densestksubgraph.
BibTeX  Entry
@InProceedings{linhares_et_al:LIPIcs:2017:7455,
author = {Andr{\'e} Linhares and Chaitanya Swamy},
title = {{Improved Algorithms for MST and MetricTSP Interdiction}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {32:132:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7455},
URN = {urn:nbn:de:0030drops74552},
doi = {10.4230/LIPIcs.ICALP.2017.32},
annote = {Keywords: Approximation algorithms, interdiction problems, LProunding algorithms, iterative rounding, treeknapsack problem, supermodular functions}
}
07.07.2017
Keywords: 

Approximation algorithms, interdiction problems, LProunding algorithms, iterative rounding, treeknapsack problem, supermodular functions 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

07.07.2017 