Journal
OPERATIONS RESEARCH LETTERS
Volume 42, Issue 6-7, Pages 450-454Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.orl.2014.07.010
Keywords
Interdiction problems; Robust optimization; Approximation algorithms; Multi-objective optimization
Categories
Funding
- NSF [CCF-1115849]
- Division of Computing and Communication Foundations
- Direct For Computer & Info Scie & Enginr [1115849] Funding Source: National Science Foundation
Ask authors/readers for more resources
We consider the problem of maximally decreasing the edge-connectivity of an edge-weighted graph by removing a limited set of edges. This problem, which we term connectivity interdiction, falls into a large family of so-called interdiction problems, which have been considered in a variety of contexts. Whereas little is known about the approximability of most interdiction problems, we show that connectivity interdiction admits a PTAS, and a natural special case of it can even be solved efficiently. (C) 2014 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
