Ant Colony Optimization (ACO) is a very popular metaheuristic for solving
computationally hard combinatorial optimization problems. Runtime analysis of
ACO with respect to various pseudo-boolean functions and different graph based
combinatorial optimization problems has been taken up in recent years. In this
paper, we investigate the runtime behavior of an MMAS*(Max-Min Ant System) ACO
algorithm on some well known hypergraph covering problems that are NP-Hard. In
particular, we have addressed the Minimum Edge Cover problem, the Minimum
Vertex Cover problem and the Maximum Weak- Independent Set problem. The
influence of pheromone values and heuristic information on the running time is
analysed. The results indicate that the heuristic information has greater
impact towards improving the expected optimization time as compared to
pheromone values. For certain instances of hypergraphs, we show that the MMAS*
algorithm gives a constant order expected optimization time when the dominance
of heuristic information is suitably increased.