Algorithm for constraint partial inverse matroid problem with weight increase forbidden

In a partial inverse matroid problem, given a matroid M = ( S, I ), a real valued weight function w on S, and an independent set I 0 ∈ I, the goal is to modify the weight w as small as possible to a new weight w ¯ such that there exists a w ¯ -maximum base containing I 0. In this paper, we study a constraint version of the partial inverse matroid problem in which the weight can only be decreased. A polynomial time algorithm is presented under l ∞ -norm.

Authors

• Shuangshuang Li
• Zhao Zhang Hefei University of Technology, Yunnan Key Laboratory of Software Engineering
• Hong-Jian Lai

Keywords

• Partial inverse optimization problem
• Matroid
• Weight constraint
• Polynomial time algorithm