# Solving Budgeted Maximum Coverage Problem using Greedy and Genetic Algorithm

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?

Assuming P≠NP, it is known that no polynomial time approximation algorithm can always give a $$1-1/e + \epsilon$$ approximation ratio, for any positive $$\epsilon$$.