Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

New for: D3
<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Ant Colony Optimization and Hypergraph Covering Problems
Speaker:Ashish Ranjan Rota
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:DAAD WISE Intern at MPI AG1
Event Type:Talk
Visibility:D1, D3, D5, SWS, D4, RG1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Wednesday, 1 June 2011
Time:11:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:3rd floor rotunda
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.

Contact
Name(s):Benjamin Doerr
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Benjamin Doerr, 05/22/2011 01:33 PM -- Created document.