License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.32
URN: urn:nbn:de:0030-drops-74552
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7455/
Go to the corresponding LIPIcs Volume Portal

Linhares, André ; Swamy, Chaitanya

Improved Algorithms for MST and Metric-TSP Interdiction

pdf-format:
LIPIcs-ICALP-2017-32.pdf (0.6 MB)

Abstract

We consider the MST-interdiction 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 w-weight of an MST of G-R:=(V,E-R).

Our main result is a 4-approximation algorithm for this problem. This improves upon the previous-best 14-approximation [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 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 analysis (and the one in [Zenklusen, FOCS 2015]).

Our guarantee for MST-interdiction yields an 8-approximation for metric-TSP interdiction (improving over the 28-approximation in [Zenklusen, FOCS 2015]). We also show that maximum-spanning-tree interdiction is at least as hard to approximate as the minimization version of densest-k-subgraph.

BibTeX - Entry

@InProceedings{linhares_et_al:LIPIcs:2017:7455,
  author =	{Andr{\'e} Linhares and Chaitanya Swamy},
  title =	{{Improved Algorithms for MST and Metric-TSP Interdiction}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{32:1--32:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7455},
  URN =		{urn:nbn:de:0030-drops-74552},
  doi =		{10.4230/LIPIcs.ICALP.2017.32},
  annote =	{Keywords: Approximation algorithms, interdiction problems, LP-rounding algorithms, iterative rounding, tree-knapsack problem, supermodular functions}
}

Keywords: Approximation algorithms, interdiction problems, LP-rounding algorithms, iterative rounding, tree-knapsack problem, supermodular functions
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI