期刊
OPERATIONS RESEARCH LETTERS
卷 42, 期 6-7, 页码 450-454出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.orl.2014.07.010
关键词
Interdiction problems; Robust optimization; Approximation algorithms; Multi-objective optimization
资金
- NSF [CCF-1115849]
- Division of Computing and Communication Foundations
- Direct For Computer & Info Scie & Enginr [1115849] Funding Source: National Science Foundation
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据