Name
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. |
Year | Venue | Field |
|---|---|---|
2017 | APPROX-RANDOM | Graph,Mathematical optimization,Algorithm,Matching (graph theory),Interdiction,3-dimensional matching,Traffic engineering,Optimization problem,Mathematics |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
8 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samuel Haney | 1 | 9 | 2.47 |
| Bruce M. Maggs | 2 | 3592 | 368.31 |
| Biswaroop Maiti | 3 | 0 | 0.34 |
| Debmalya Panigrahi | 4 | 269 | 35.78 |
| Rajmohan Rajaraman | 5 | 2038 | 250.08 |
| Ravi Sundaram | 6 | 762 | 72.13 |