Weighted Inverse Minimum Cut Problem under the Sum-Type Hamming Distance

摘要

An inverse optimization problem is defined as follows: Let 5 denote the set of feasible solutions of an optimization problem P, let c be a specified cost (capacity) vector , and x~0 ∈ S. We want to perturb the cost (capacity) vector c to d such that x~0 becomes an optimal solution of P with respect to the cost (capacity) vector d, and to minimize some objective functions. In this paper, we consider the weighted inverse minimum cut problem under the sum-type Hamming distance. First, we show the general case is NP-hard. Second we present a combinatorial algorithm that run in strongly polynomial time to solve a special case.