A Weighted Inverse Minimum s − t Cut Problem with Value Constraint Under the Bottleneck-Type Hamming Distance

Elham Ramzani Ghalebala (), Massoud Aman and Nasim Nasrabadi ()
Additional contact information
Elham Ramzani Ghalebala: Department of Mathematics, Faculty of Mathematics and Statistics, University of Birjand, Khorasan-e-Jonobi, Birjand, Iran
Massoud Aman: Department of Mathematics, Faculty of Mathematics and Statistics, University of Birjand, Khorasan-e-Jonobi, Birjand, Iran
Nasim Nasrabadi: Department of Mathematics, Faculty of Mathematics and Statistics, University of Birjand, Khorasan-e-Jonobi, Birjand, Iran

Asia-Pacific Journal of Operational Research (APJOR), 2024, vol. 41, issue 01, 1-22

Abstract: Given a network G = (N,A,c) and an s − t cut [S,S̄] with the capacity β and the constant value α, an inverse minimum s − t cut problem with value constraint is to modify the vector capacity c as little as possible to make the s − t cut [S,S̄] become a minimum s − t cut with the capacity α. The distinctive feature of this problem with the inverse minimum cut problems is the addition of a constraint in which the capacity of the given cut has to equal to the preassumed value α. In this paper, we investigate the inverse minimum s − t cut problem with value constraint under the bottleneck weighted Hamming distance. We propose two strongly polynomial time algorithms based on a binary search to solve the problem. At each iteration of the first one, we solve a feasible flow problem. The second algorithm considers the problem in two cases β > α and β < α. In this algorithm, we first modify the capacity vector such that the given cut becomes a minimum s − t cut in the network and then, by preserving optimality this s − t cut, adjust it to satisfy value constraint.

Keywords: Inverse problem; bottleneck-type Hamming distance; binary search; strongly polynomial time algorithm (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595923500094
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:41:y:2024:i:01:n:s0217595923500094

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595923500094

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().