Hardness and approximation for network flow interdiction
| Autor: | Rico Zenklusen, Stephen R. Chestnut |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
FOS: Computer and information sciences
Polynomial Computer Networks and Communications Computer science 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology Hardness of approximation 01 natural sciences Computer Science::Discrete Mathematics Computer Science - Data Structures and Algorithms FOS: Mathematics Data Structures and Algorithms (cs.DS) Mathematics - Optimization and Control Time complexity Discrete mathematics 021103 operations research Approximation algorithm Interdiction Flow network Complement (complexity) Optimization and Control (math.OC) 010201 computation theory & mathematics Hardware and Architecture Graph (abstract data type) Software Information Systems |
| Zdroj: | Networks. 69:378-387 |
| ISSN: | 0028-3045 |
| Popis: | In the Network Flow Interdiction problem, an adversary attacks a network in order to minimize the maximum s-t-flow. Very little is known about the approximatibility of this problem, despite decades of interest in it. It is, surprisingly, nontrivial to obtain in polynomial time an approximation guarantee that is independent of the number of edges in the graph and their capacities. We present the first such approximation algorithm, which has approximation ratio at most 2(n−1) for any graph with n vertices. We complement the algorithm with a hardness theorem. Past work has shown that Network Flow Interdiction cannot be much easier to approximate than Densest k-Subgraph. We show that any nϵ-approximation algorithm for Network Flow Interdiction, or one of several variants, would imply a 2n4ϵ-approximation algorithm for Densest k-Subgraph, which is an improvement over past work in terms of the polynomial factor. We also show that Network Flow Interdiction is essentially the same as the Budgeted Minimum s-t-Cut problem, and transferring our results gives hardness and an approximation algorithm for that problem, as well. © 2017 Wiley Periodicals, Inc. NETWORKS, 2017 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text