This paper studies the maximization of a polymatroid subject to a cardinality constraint. In particular, we consider the problem of improving the value of the greedy set by swapping one of its members with an element that does not belong to it. To achieve this goal, we first define a (set-based) post-greedy measure of curvature of a polymatroid. Then we use it to build a non-recursive test that, in polynomial time, provides sufficient conditions for the greedy collection to be ‘locally’ optimal. Finally, we generalize our test by considering larger swaps of elements and verify that, as the number of swapped elements increases, the likelihood for the greedy collection to remain locally maximnal deteriorates.
Citation
Area of Operations Decision Sciences IE Business School/University P.º de la Castellana, 259 28046, Madrid, Spain msoffritti@nebrija.es