The optimal base of a matroid with three-type constraints
type: Item
instance of: scholarly article
title: The optimal base of a matroid with three-type constraints
zbMATH Open document ID: 0671.05018
DOI: 10.1007/BF02006057
author: Jue Xue
published in: Acta Mathematicae Applicatae Sinica. English Series
publication date: 1988-01-01T00:00:00Z
review text: 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)].)
reviewed by: András Recski
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 4097395
zbMATH Keywords: maximum weight base
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/bf02006057
OpenAlex ID: W2019535041
description: scientific article; zbMATH DE number 4097395