Symmetric interdiction for matching problems

Published

Conference Paper

© Samuel Haney, Bruce Maggs, Biswaroop Maiti, Debmalya Panigrahi, Rajmohan Rajaraman, and Ravi Sundaram. 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.

Full Text

Duke Authors

Cited Authors

  • Haney, S; Maggs, B; Maiti, B; Panigrahi, D; Rajaraman, R; Sundaram, R

Published Date

  • August 1, 2017

Published In

Volume / Issue

  • 81 /

International Standard Serial Number (ISSN)

  • 1868-8969

International Standard Book Number 13 (ISBN-13)

  • 9783959770446

Digital Object Identifier (DOI)

  • 10.4230/LIPIcs.APPROX/RANDOM.2017.9

Citation Source

  • Scopus