2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

Absolutely they can. The approximation algorithms give a formal guarantee that the solution won't be too bad and they quantify what this means whereas with a metaheuristic such as GA all bets are off. Really, the only guarantee you have with GA is that the solution is valid, but that's it.

Your best bet is to just implement the GA and give it a try. Much will depend on the details and choices you make inside the method as well as on your instances and their structure.

$\endgroup$
2
$\begingroup$

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$.

However, this is a worst-case hardness result. In real life, instances are typically not worst-case, and therefore you can get better guarantees in practice. This holds not only for genetic algorithms, but also for more standard algorithms, including various greedy strategies, which might perform much better in practice than their worst-case approximation guarantees.

With current mathematical technology, the only way to truly assess an approximation heuristic is to try it out on real data.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.