We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A Weighted Inverse Minimum s−t Cut Problem with Value Constraint Under the Bottleneck-Type Hamming Distance.
- Authors
Ghalebala, Elham Ramzani; Aman, Massoud; Nasrabadi, Nasim
- 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.
- Subjects
HAMMING distance; CUTTING stock problem; POLYNOMIAL time algorithms; HAMMING weight; INVERSE problems
- Publication
Asia-Pacific Journal of Operational Research, 2024, Vol 41, Issue 1, p1
- ISSN
0217-5959
- Publication type
Article
- DOI
10.1142/S0217595923500094