I am trying to solve the Budgeted Maximum Coverage Problem.
I have read and implemented the greedy and modified-greedy methods to solve it, as proposed by Khuller.
Both are approximation algorithms. The greedy provides a $1/2(1-1/e)$ approximation, and the modified greedy guarantees $1-1/e$.
I am trying to get better results than this using a genetic algorithm. However, I am not sure if that is at all possible.
My question is, can GA (or any metaheuristics) provide better results? Or is trying such a thing futile?