Algorithm For Constraint Partial Inverse Matroid Problem

In a partial inverse matroid problem, given a matroid M =（S, L）, a weight function w on S, and an independent set I₀∈L, the goal is to modify weight w as small as possible to a new weight （?） such that there exists a （?）-maximum base containing I₀. In this paper,we study a constraint version of the partial inverse matroid problem in which the weight can only be increased（denoted as CPIM⁺） or be decreased（denoted as CPIM^-）. Two polynomial time algorithms are presented for CPIM⁺when the modification is measured by any monotone nondecreasing norm. A polynomial time algorithm is presented for CPIM^-under l_∞-norm.