1 Search Results for "Linhares, André"

Improved Algorithms for MST and Metric-TSP Interdiction

Authors: André Linhares and Chaitanya Swamy

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

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.

Cite as

André Linhares and Chaitanya Swamy. Improved Algorithms for MST and Metric-TSP Interdiction. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

  author =	{Linhares, Andr\'{e} and Swamy, Chaitanya},
  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 =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.32},
  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}
  • Refine by Author
  • 1 Linhares, André
  • 1 Swamy, Chaitanya

  • Refine by Classification

  • Refine by Keyword
  • 1 Approximation algorithms
  • 1 LP-rounding algorithms
  • 1 interdiction problems
  • 1 iterative rounding
  • 1 supermodular functions
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail