Inverse matroid optimization problem under the weighted Hamming distances inverse minimum cost flow problem under the bottleneck-type Hamming distance

Abstract

Given a matroid equipped with a utility vector to de_ne a matroid optimization problem, the corresponding inverse problem is to modify the utility vector as little as possible so that a given base of the matroid becomes optimal to the matroid optimization problem. The modifications can be measured by various distances. In this article, we consider the inverse matroid problem under the bottleneck-type and the sum-type weighted Hamming distances. In the sum-type case, the problem is converted into a minimum weighted node covering the problem on a bipartite network and consequently, it can be solved in strongly polynomial time. In the bottleneck case, we propose an algorithm based on the binary search technique to solve the problem in strongly polynomial time.