Document Open Access Logo

Improved Algorithms for MST and Metric-TSP Interdiction

Authors André Linhares, Chaitanya Swamy

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.32.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

André Linhares
Chaitanya Swamy

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.ICALP.2017.32

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.

Subject Classification

Keywords
  • Approximation algorithms
  • interdiction problems
  • LP-rounding algorithms
  • iterative rounding
  • tree-knapsack problem
  • supermodular functions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. N. Assimakopoulos. A network interdiction model for hospital infection control. Computers in Biology and Medicine, 17(6):413-422, 1987. Google Scholar
  2. C. Burch, R. Carr, S. Krumke, M. Marathe, C. Phillips, and E. Sundberg. A decomposition-based pseudoapproximation algorithm for network flow inhibition. In Network Interdiction and Stochastic Integer Programming, chapter 3, pages 51-68. Springer, 2003. Google Scholar
  3. S. Chestnut and R. Zenklusen. Hardness and approximation for network flow interdiction. CS arXiv, November 2015. Google Scholar
  4. S. Chestnut and R. Zenklusen. Interdicting structured combinatorial optimization problems with 0,1-objectives. CS arXiv, November 2015. Google Scholar
  5. R. L. Church, M. P. Scaparra, and R. S. Middleton. Identifying critical infrastructure: the median and covering facility interdiction problems. Annals of the Association of American Geographers, 94(3):491-502, 2004. Google Scholar
  6. M. Dinitz and A. Gupta. Packing interdiction and partial covering problems. In Proceedings of 16th IPCO, pages 157-168, 2013. Google Scholar
  7. A. Engelberg, J. Könemann, S. Leonardi, and J. Naor. Cut problems in graphs with a budget constraint. Journal of Discrete Algorithms, 5:262-279, 2007. Google Scholar
  8. L. Fleischer and S. Iwata. A push-relabel framework for submodular function minimization and applications to parametric optimization. Discrete Applied Mathematics, 131(2):311-322, 2003. Google Scholar
  9. G. N. Frederickson and R. Solis-Oba. Increasing the weight of minimum spanning trees. Journal of Algorithms, 33:244-266, 1999. Google Scholar
  10. D. R. Fulkerson and G. C. Harding. Maximizing the minimum source-sink path subject to a budget constraint. Math. Programming, 13:116-118, 1977. Google Scholar
  11. P. M. Ghare, D. C. Montgomery, and W. C. Turner. Optimal interdiction policy for a flow network. Naval Research Logistics Quarterly, 18:37-45, 1971. Google Scholar
  12. F. Grandoni, R. Ravi, M. Singh, and R. Zenklusen. New approaches to multi-objective optimization. Mathematical Programming, 146(1-2):525-554, 2014. Google Scholar
  13. G. Guruganesh, L. Sanità, and C. Swamy. Improved region-growing and combinatorial algorithms for k-route cut problems. In Proceedings of SODA, pages 676-695, 2015. Google Scholar
  14. E. Israeli and R. K. Wood. Shortest-path network interdiction. Networks, 40:97-111, 2002. Google Scholar
  15. D. S. Johnson and K. A. Niemi. On knapsacks, partitions, and a new dynamic programming technique for trees. Math. of Oper. Research, 8(1):1-14, 1983. Google Scholar
  16. G. Joret and A. Vetta. Reducing the rank of a matroid. Discrete Mathematics & Theoretical Computer Science, 17(2):143-156, 2015. Google Scholar
  17. L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, G. Rudolf, and J. Zhao. On short paths interdiction problems: total and node-wise limited interdiction. Theoretical Computer Science, 43(2):204-233, 2008. Google Scholar
  18. S. Kolliopoulos and G. Steiner. Partially-ordered knapsack and applications to scheduling. Discrete Applied Mathematics, 155(8):889-897, 2007. Google Scholar
  19. J. Könemann, O. Parekh, and D. Segev. A unified approach to approximating partial covering problems. Algorithmica, 59(4):489-509, 2011. Google Scholar
  20. Euiwoong Lee. Improved hardness for cut, interdiction, and firefighter problems. CS arXiv, July 2016. Google Scholar
  21. W. Liang. Finding the k most vital edges with respect to minimum spanning trees for fixed k. Discrete Applied Mathematics, 113(2-3):319-327, 2001. Google Scholar
  22. K. Liri and M. Chern. The most vital edges in the minimum spanning tree problem. Information Processing Letters, 45:25-31, 1993. Google Scholar
  23. K. Nagano. A faster parametric submodular function minimization algorithm and applications. Technical report, University of Tokyo, 2007. METR 2007-43. Google Scholar
  24. F. Pan, W. Charlton, and D. P. Morton. Stochastic network interdiction of nuclear material smuggling. In D.L. Woodruff, editor, Network Interdiction and Stochastic Integer Programming, pages 1-19. Kluwer Academic Publishers, 2002. Google Scholar
  25. C. A. Phillips. The network inhibition problem. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), pages 776-785, 1993. Google Scholar
  26. P. Raghavendra and D. Steurer. Graph expansion and the unique games conjecture. In Proceedings of the 42nd STOC, pages 755-764, 2010. Google Scholar
  27. J. Salmeron, K. Wood, and R. Baldick. Worst-case interdiction analysis of large-scale electric power grids. IEEE Trans. on Power Systems, 24(1):96-104, 2009. Google Scholar
  28. R. K. Wood. Deterministic network interdiction. Mathematical and Computer Modeling, 17(2):1-18, 1993. Google Scholar
  29. R. Zenklusen. Matching interdiction. Discrete App. Math., 158:1676-1690, 2010. Google Scholar
  30. R. Zenklusen. Network flow interdiction on planar graphs. Discrete Applied Mathematics, 158(13):1441-1455, 2010. Google Scholar
  31. R. Zenklusen. An O(1)-approximation for minimum spanning tree interdiction. In Proceedings of the 56th FOCS, pages 709-728, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact