|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
On the Bicriterion Maximum Flow Network Interdiction Problem | | Luca E. Schäfer
; Stefan Ruzika
; Sven O. Krumke
; Carlos M. Fonseca
; | | Date: |
6 Oct 2020 | | Abstract: | This article focuses on a biobjective extension of the maximum flow network
interdiction problem, where each arc in the network is associated with two
capacity values. Two maximum flows from source to sink are to be computed
independently of each other with respect to the first and second capacity
function, respectively, while an interdictor aims to minimize the value of both
maximum flows by interdicting arcs. We show that this problem is intractable
and that the decision problem, which asks whether or not a feasible
interdiction strategy is efficient, is NP-complete. We propose a
pseudopolynomial time algorithm in the case of two-terminal series-parallel
graphs and positive integer-valued interdiction costs. We extend this algorithm
to a fully polynomial-time approximation scheme for the case of unit
interdiction costs by appropriately partitioning the objective space. | | Source: | arXiv, 2010.02730 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER