Extending Polymatroid Set Functions With Curvature and Bounding the Greedy Strategy

Consider the problem of choosing a set of actions to optimize a real-valued polymatroid function subject to matroid constraints. The greedy strategy provides an approximate solution to the optimization problem, and it is known to satisfy some performance bounds in terms of the total curvature. But the total curvature depends on the values of the objective function on sets outside the matroid. If we are given a function defined only on the matroid, the problem still makes sense, but the existing bounds involving the total curvature do not apply. This motivates an alternative formulation of such bounds. We provide necessary and sufficient conditions for the existence of an extension of a polymatroid function defined on the matroid to one defined on the whole power set. Our results give rise to bounds for systems satisfying the necessary and sufficient conditions, which apply to problems where the objective function is defined only on the matroid. When the objective function is defined on the entire power set, the bounds we derive in general improve over the previous ones. To illustrate our results, we present a task scheduling problem.