This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
teaching:mfe:ia [2015/04/11 17:37] stuetzle [Design of a graphical interface for an automatic configuration tool.] |
teaching:mfe:ia [2015/04/11 17:38] stuetzle [Analysis of Local Optima Networks for the Max-Clique problem.] |
||
|---|---|---|---|
| Line 229: | Line 229: | ||
| * [[http://iridia.ulb.ac.be/~fmascia|Franco Mascia (IRIDIA)]] | * [[http://iridia.ulb.ac.be/~fmascia|Franco Mascia (IRIDIA)]] | ||
| - | |||
| - | ===== Analysis of Local Optima Networks for the Max-Clique problem. ====== | ||
| - | |||
| - | Stochastic Local Search algorithms search for optimal solutions in a large space of candidate solutions. Local Optima Networks (LON) are representations of search landscapes of combinatorial optimisation problems. In these networks, nodes are local optima of the problem, and edges are weighted transitions between the optima. These networks model in a more compact way the properties of the larger search spaces they represent. | ||
| - | |||
| - | The goal of this project is to build LON of small instances of the Maximum Clique (MC) problem, and measure properties that could illustrate the differences between instance families. | ||
| - | |||
| - | The MC problem is an NP-hard combinatorial optimisation problem that asks to find the biggest completely connected component of a graph. It has relevant applications in information retrieval, computer vision, social network analysis, computational biochemistry, bioinformatics and genomics. | ||
| - | |||
| - | |||
| - | Required skills: good knowledge of C or C++ programming. | ||
| - | |||
| - | |||
| - | * Contacts : | ||
| - | * [[http://iridia.ulb.ac.be/~stuetzle|Thomas Stützle (IRIDIA)]] | ||
| - | * [[http://iridia.ulb.ac.be/~fmascia|Franco Mascia (IRIDIA)]] | ||