Document Open Access Logo

Symmetric Interdiction for Matching Problems

Authors Samuel Haney, Bruce Maggs, Biswaroop Maiti, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.9.pdf
  • Filesize: 0.69 MB
  • 19 pages

Document Identifiers

Author Details

Samuel Haney
Bruce Maggs
Biswaroop Maiti
Debmalya Panigrahi
Rajmohan Rajaraman
Ravi Sundaram

Cite As Get BibTex

Samuel Haney, Bruce Maggs, Biswaroop Maiti, Debmalya Panigrahi, Rajmohan Rajaraman, and Ravi Sundaram. Symmetric Interdiction for Matching Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.9

Abstract

Motivated by denial-of-service network attacks, we introduce the symmetric interdiction model, where both the interdictor and the optimizer are subject to the same constraints of the underlying optimization problem. We give a general framework that relates optimization to symmetric interdiction for a broad class of optimization problems. We then study the symmetric matching interdiction problem - with applications in traffic engineering - in more detail. This problem can be simply stated as follows: find a matching whose removal minimizes the size of the maximum matching in the remaining graph. We show that this problem is APX-hard, and obtain a 3/2-approximation algorithm that improves on the approximation guarantee provided by the general framework.

Subject Classification

Keywords
  • Approximation algorithms
  • matching
  • interdiction Digital Object

Metrics

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

References

  1. Douglas S. Altner, Özlem Ergun, and Nelson A. Uhan. The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability. Operations Research Letters, 38(1):33-38, 2010. Google Scholar
  2. Imre Bárány and Roman Karasev. Notes about the carathéodory number. Discrete &Computational Geometry, 48(3):783-792, 2012. Google Scholar
  3. Piotr Berman and Marek Karpinski. On some tighter inapproximability results. In International Colloquium on Automata, Languages, and Programming, pages 200-209. Springer, 1999. Google Scholar
  4. Stephen R. Chestnut and Rico Zenklusen. Interdicting structured combinatorial optimization problems with 0, 1-objectives. Mathematics of Operations Research, 2016. Google Scholar
  5. Stephen R. Chestnut and Rico Zenklusen. Hardness and approximation for network flow interdiction. Networks, 2017. Google Scholar
  6. Richard L. Church, Maria P. Scaparra, and Richard 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
  7. Eugene Peter Durbin. An interdiction model of highway transportation. Rand Memorandum, 1966. Google Scholar
  8. Greg N. Frederickson and Roberto Solis-Oba. Increasing the weight of minimum spanning trees. Journal of Algorithms, 33(2):244-266, 1999. Google Scholar
  9. P. M. Ghare, Douglas C. Montgomery, and W. C. Turner. Optimal interdiction policy for a flow network. Naval Research Logistics Quarterly, 18(1):37-45, 1971. Google Scholar
  10. Bruce Golden. A problem in network interdiction. Naval Research Logistics Quarterly, 25(4):711-713, 1978. Google Scholar
  11. Martin Grötschel, Lászlo Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer, second corrected edition edition, 1993. Google Scholar
  12. Alpár Jüttner. On budgeted optimization problems. SIAM Journal on Discrete Mathematics, 20(4):880-892, 2006. Google Scholar
  13. Rafael R. Kamalian and Vahan V. Mkrtchyan. Two polynomial algorithms for special maximum matching constructing in trees. arXiv preprint arXiv:0707.2295, 2007. Google Scholar
  14. Rafael R. Kamalian and Vahan V. Mkrtchyan. On complexity of special maximum matchings constructing. Discrete Mathematics, 308(10):1792-1800, 2008. Google Scholar
  15. Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, Gabor Rudolf, and Jihui Zhao. On short paths interdiction problems: Total and node-wise limited interdiction. Theory of Computing Systems, 43(2):204-233, 2008. Google Scholar
  16. Churlzu Lim and J. Cole Smith. Algorithms for discrete and continuous multicommodity flow network interdiction problems. IIE Transactions, 39(1):15-26, 2007. Google Scholar
  17. Rui Miao, Rahul Potharaju, Minlan Yu, and Navendu Jain. The Dark menace: Characterizing network-based attacks in the cloud. In Proceedings of the 2015 ACM Internet Measurement Conference, 2015. Google Scholar
  18. Manfred W. Padberg and M. R. Rao. Odd minimum cut-sets and b-matchings. Mathematics of Operations Research, 7(1):67-80, 1982. URL: http://dx.doi.org/10.1287/moor.7.1.67.
  19. Jörg Rambau. On a generalization of schönhardt’s polyhedron. Combinatorial and computational geometry, 52:510-516, 2003. Google Scholar
  20. Alexander Schrijver. On the history of the transportation and maximum flow problems. Mathematical Programming, 91(3):437-445, 2002. Google Scholar
  21. Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency. Vol. A. Paths, flows, matchings. Chapters 1-38. Algorithms and combinatorics. Springer-Verlag, 2003. URL: http://opac.inria.fr/record=b1100334.
  22. F Bruce Shepherd and Adrian Vetta. The demand-matching problem. Mathematics of Operations Research, 32(3):563-578, 2007. Google Scholar
  23. Adrian Vetta and Gwenaël Joret. Reducing the rank of a matroid. Discrete Mathematics &Theoretical Computer Science, 17, 2015. Google Scholar
  24. Heinrich Von Stackelberg. Market structure and equilibrium. Springer Science &Business Media, 2010. Google Scholar
  25. R. Kevin Wood. Deterministic network interdiction. Mathematical and Computer Modelling, 17(2):1-18, 1993. Google Scholar
  26. Rico Zenklusen. Matching interdiction. Discrete Applied Mathematics, 158(15):1676-1690, 2010. Google Scholar
  27. Rico Zenklusen. Network flow interdiction on planar graphs. Discrete Applied Mathematics, 158(13):1441-1455, 2010. Google Scholar
  28. Rico Zenklusen. An o(1)-approximation for minimum spanning tree interdiction. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 709-728. IEEE, 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