Let M1 and M2 be matroids on S, B be their k-element common independent set, and w a weight function on S. Given two functions b ≥ 0 and c ≥ 0 on S, the Inverse Matroid Intersection Problem (IMIP) is to determine a modified weight function w′ such that (a) B becomes a maximum weight common independent set of cardinality k under w′, (b) c|w′ – w| is minimum, and (c) |w′ – w| ≤ b. Many Inverse Combinatorial Optimization Problems can be considered as the special cases of the IMIP. In this paper we show that the IMIP can be solved in strongly polynomial time, and give a necessary and sufficient condition for the feasibility of the IMIP. Finally we extend the discussion to the version of the IMIP with Multiple Common Independent Sets.
