Campus Event Calendar
Event Entry
New for: D3
What and Who
Ant Colony Optimization and Hypergraph Covering Problems
Ashish Ranjan Rota
Max-Planck-Institut für Informatik - D1
Talk
DAAD WISE Intern at MPI AG1
AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 1 June 2011
11:00
30 Minutes
E1 4
3rd floor rotunda
Saarbrücken
Abstract
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.
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.
Contact
Benjamin Doerr
--email hidden
passcode not visible
logged in users only
Benjamin Doerr, 05/22/2011 13:33 -- Created document.