[Home ] [Archive]    
:: Main :: About :: Current Issue :: Archive :: Search :: Submit :: Registration ::
Main Menu
Home::
Journal Information::
Articles archive::
Submission Instruction::
Registration::
Submit article::
Site Facilities::
Contact us::
::
Google Scholar

Citation Indices from GS

AllSince 2019
Citations85823613
h-index127
i10-index136

Search in website

Advanced Search
Receive site information
Enter your Email in the following box to receive the site news and information.
:: Volume 5, Issue 2 (10-2014) ::
IJOR 2014, 5(2): 0-0 Back to browse issues page
Capacity Inverse Minimum Cost Flow Problem under the Weighted Hamming Distances
M Aman , J Tayyebi
Mathematics Department , javadtayyebi@birjand.ac.ir
Abstract:   (25947 Views)

Given an instance of the minimum cost flow problem, a version of the corresponding inverse problem, called the capacity inverse problem, is to modify the upper and lower bounds on arc flows as little as possible so that a given feasible flow becomes optimal to the modified minimum cost flow problem. The modifications can be measured by different distances. In this article, we consider the capacity inverse problem under the bottleneck-type and the sum-type weighted Hamming distances. In the bottleneck-type case, the binary search technique is applied to present an algorithm for solving the problem in O(nm log n) time. In the sum-type case, it is shown that the inverse problem is strongly NP-hard even on bipartite networks

Keywords: Combinatorial optimization, minimum cost flow problem, inverse problem, Hamming distance, complexity
Full-Text [PDF 623 kb]   (31295 Downloads)    
Type of Study: Original | Subject: Discrete Optimization
Received: 2015/04/15 | Accepted: 2015/06/17 | Published: 2015/06/17
Send email to the article author

Add your comments about this article
Your username or Email:

CAPTCHA


XML     Print



Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Volume 5, Issue 2 (10-2014) Back to browse issues page
مجله انجمن ایرانی تحقیق در عملیات Iranian Journal of Operations Research
Persian site map - English site map - Created in 0.07 seconds with 39 queries by YEKTAWEB 4645