Optimization Online


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

Mirco Soffritti(msoffritti***at***nebrija.es)

Abstract: We study the problem of maximization of a polymatroid subject to a cardinality constraint. When the set of elements to be considered is large, the greedy algorithm is the most natural heuristic for producing an approximate solution. With the greedy set in hand, we may desire to improve its value by swapping one or more of its elements with a corresponding number of elements that do not belong to it. Even though there is no guarantee that such a swap will succeed at improving the greedy solution, we define a (set-based) post-greedy measure of curvature of a polymatroid and utilize it to design a non-recursive test that, in polynomial time, provides sufficient conditions for the greedy collection to be ‘locally’ optimal. We verify that as the number of swapped elements increases, the likelihood for the greedy collection to remain locally optimal deteriorates. In other words, the probability of locally producing a feasible and better solution enhances.

Keywords: polymatroid, discrete maximization, greedy algorithm, cardinality constraint, local search, swaps, and post-greedy curvature

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Approximation Algorithms )

Category 3: Combinatorial Optimization (Meta Heuristics )

Citation: Mirco Soffritti School of Arts and Science Department of Business and Economics Antonio de Nebrija University Madrid, 28015, Spain. msoffritti@nebrija.es

Download: [PDF]

Entry Submitted: 01/20/2021
Entry Accepted: 01/20/2021
Entry Last Modified: 01/20/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society