Skip to main content

Symmetric interdiction for matching problems

Publication ,  Conference
Haney, S; Maggs, B; Maiti, B; Panigrahi, D; Rajaraman, R; Sundaram, R
Published in: Leibniz International Proceedings in Informatics, LIPIcs
August 1, 2017

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.

Duke Scholars

Published In

Leibniz International Proceedings in Informatics, LIPIcs

DOI

ISSN

1868-8969

ISBN

9783959770446

Publication Date

August 1, 2017

Volume

81
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Haney, S., Maggs, B., Maiti, B., Panigrahi, D., Rajaraman, R., & Sundaram, R. (2017). Symmetric interdiction for matching problems. In Leibniz International Proceedings in Informatics, LIPIcs (Vol. 81). https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2017.9
Haney, S., B. Maggs, B. Maiti, D. Panigrahi, R. Rajaraman, and R. Sundaram. “Symmetric interdiction for matching problems.” In Leibniz International Proceedings in Informatics, LIPIcs, Vol. 81, 2017. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2017.9.
Haney S, Maggs B, Maiti B, Panigrahi D, Rajaraman R, Sundaram R. Symmetric interdiction for matching problems. In: Leibniz International Proceedings in Informatics, LIPIcs. 2017.
Haney, S., et al. “Symmetric interdiction for matching problems.” Leibniz International Proceedings in Informatics, LIPIcs, vol. 81, 2017. Scopus, doi:10.4230/LIPIcs.APPROX/RANDOM.2017.9.
Haney S, Maggs B, Maiti B, Panigrahi D, Rajaraman R, Sundaram R. Symmetric interdiction for matching problems. Leibniz International Proceedings in Informatics, LIPIcs. 2017.

Published In

Leibniz International Proceedings in Informatics, LIPIcs

DOI

ISSN

1868-8969

ISBN

9783959770446

Publication Date

August 1, 2017

Volume

81