Local search and swapping strategies.Challenging the greedy maximization of a polymatroid subject to a cardinality constraint

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

Article

Download

View Local search and swapping strategies.Challenging the greedy maximization of a polymatroid subject to a cardinality constraint