Algorithms for the partial inverse matroid problem in which weights can only be increased (Q312484): Difference between revisions

This article introduces a constrained partial inverse matroid problem, some theoretical exposition, and two low-order polynomial time algorithms to solve the problem. The problem is as follows: given a matroid \((S,\mathcal{I})\), two non-negative weight functions \(w\) and \(b\) on the matroid's ground set \(S\), and an independent set \(I_0\) of the matroid, we seek the weight function \(\hat w\) which minimises some norm \(\|\hat w-w\|\), subject to the box constraint \(w(x)\leq\bar w(x)\leq w(x)+b(x)\) for all \(x\in S\), and to the inverse constraint, that \(I_0\) is contained in some \(\bar w\)-maximal basis of \(M\). The article contains pseudocode and complexity proofs, but no applications or numerical results.