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 [2019/04/03 16:53] bersini |
teaching:mfe:ia [2019/05/06 13:45] bersini |
||
|---|---|---|---|
| Line 61: | Line 61: | ||
| Ce mémoire se fera en collaboration avec des responsables marketing de cette société. Il consistera en l'analyse informatisée des appréciations récoltées sur les produits de la firme et d'une analyse comparative avec les appréciations de concurrents. Il s'agira pour l'essentiel d'études de type "clustering", "classification" et "sentiment analysis" au départ de nombreuses librairies déjà existantes. | Ce mémoire se fera en collaboration avec des responsables marketing de cette société. Il consistera en l'analyse informatisée des appréciations récoltées sur les produits de la firme et d'une analyse comparative avec les appréciations de concurrents. Il s'agira pour l'essentiel d'études de type "clustering", "classification" et "sentiment analysis" au départ de nombreuses librairies déjà existantes. | ||
| + | |||
| + | * Contact : [[http://code.ulb.ac.be/iridia.people.php?id=1|Hugues Bersini (IRIDIA)]] | ||
| + | |||
| + | ==== Speed-up techniques for shortest path problem ==== | ||
| + | |||
| + | |||
| + | The shortest path problem is one of the most important in combinatorial optimization and has multiple real-world applications. | ||
| + | The well-known Dijkstra algorithm solves the shortest path problem in any weighted graph with non-negative weights. However, with the recent increase of the amount of data, we feel the need to drastically increase the execution time of the algorithm. | ||
| + | In the latest years, we observe the emergence of a lot of new speed-up techniques; among them there are: heuristic search, bidirectional search, landmarks, reaches, short-cuts and contractions. The efficiency of these techniques heavily depends on the topology of the graph. Moreover, graphs with more complex structures (as user-adapted graphs) do not support some of these techniques, at least as they are currently presented. | ||
| + | From these observations, several questions arise, among them we propose: | ||
| + | Which optimization methods are the most efficient depending on the graph topology? | ||
| + | How can we adapt these techniques to more complex graph structures? | ||
| + | Other research questions in this topic can be proposed and discussed. | ||
| + | These questions can be studied from both theoretical and empirical approach. | ||
| * Contact : [[http://code.ulb.ac.be/iridia.people.php?id=1|Hugues Bersini (IRIDIA)]] | * Contact : [[http://code.ulb.ac.be/iridia.people.php?id=1|Hugues Bersini (IRIDIA)]] | ||