Greedily Excluding Algorithm for Submodular Maximization

This paper develops an approximation algorithm for maximization of monotone submodular reward function with a cardinality constraint. The main focus of our development is to enhances the level of guaranteed optimality, computational complexity or both compared with the well-known existing greedy based approaches. The proposed algorithm is called the greedily excluding algorithm. In this algorithm, an element is removed from the ground set to find the solution set and this allows the algorithm to improve both the optimality level and computational complexity for a problem with a high cardinality constraint. The characteristics of the proposed algorithm are mathematically analysed and compared with those of well-known greedy-based algorithms. A case study is also carried out to demonstrate the performance of the approximation algorithms developed.