A weighted inverse minimum cut problem under the bottleneck type hamming distance

作者：Liu Longcheng^*; Yao Enyu

来源：Asia Pacific Journal of Operational Research, 2007, 24(5): 725-736.

DOI：10.1142/S0217595907001474

• minimum cut
• inverse problem
• hamming distance
• strongly polynomial algorithm

An inverse optimization problem is defined as follows. Let S denote the set of feasible solutions of an optimization problem P, let c be a specified cost (capacity) vector, and x(0) is an element of S. We want to perturb the cost (capacity) vector c to d so that x(0) is an optimal solution of P with respect to the cost (capacity) vector d, and to minimize some objective function. In this paper, we consider the weighted inverse minimum cut problem under the bottleneck type Hamming distance. For the general case, we present a combinatorial algorithm that runs in strongly polynomial time.

• 出版日期2007-10
• 单位浙江大学