The optimal base of a matroid with three-type constraints (Q1119653)

Finding a maximum weight base B in a matroid, subject to \(a_ i\leq | B\cap X_ i| \leq b_ i\) for every \(X_ i\in {\mathcal X}\) and \(a_ i\leq b_ i\leq | X_ i|\) is easy if \({\mathcal X}\) is a partition and is NP-hard if \({\mathcal X}\) is arbitrary, see \textit{Ma Zhong-fan}, \textit{Liu Zhen-hong} and \textit{Cai Mao-cheng}, Optimum restricted base of a matroid, Sci. Sin. 12, 1148-1156 (1979), see also Ann. Discrete Math. 9, 253-257 (1980; Zbl 0445.05036), for example. The author gives a polynomial algorithm if \(X_ 1,X_ 2\in {\mathcal X}\), \(X_ 1\cap X_ 2\neq \emptyset\) implies \(X_ 1\subseteq X_ 2\) or \(X_ 2\subseteq X_ 1\). (This result as well as some stronger ones follow from results of \textit{A. Frank} and \textit{E. Tardos} [Generalized polymatroids and submodular flows, Math. Program., Ser. B 42, No.3, 489-563 (1988)].)