A rounding technique for the polymatroid membership problem (Q1893104)

Let \(E\) be a finite set and \(\rho\) a polymatroid rank function on \(E\). The polyhedron \(P_\rho\) is the set of all nonnegative vectors \(x: E\to R\) such that \(x(X)= \sum_{e\in X} x(e)\leq \rho(X)\), \(X\subset E\). The membership problem is to determine if a fixed vector \(w: E\to R\) is in \(P_\rho\), and if not, to find a subset \(X\) of \(E\) that maximizes \(w(X)- \rho(X)\), \(X\subset E\). This paper contains a technique for finding a subset which maximizes \(w(X)- \rho(X)\) over all subsets of the set \(E\), where \(w\) and \(\rho\) are real modular and polymatroid functions, resp., using as a subroutine an algorithm which finds such a set for another pair of functions which are near \(w\), \(\rho\), respectively. This technique gives an \(O(|E|^3 r^2)\) algorithm in the case when \(\rho\) is a matroid rank function.