Des chercheurs du MIT créent KLOS
Un puissant algorithme de parcours de graphes non orientés
Le 2014-01-10 05:44:12, par Cedric Chevalier, Expert éminent sénior
Qu’est ce qu’un graphe ? Des points et des lignes. En tout cas, c’est la réponse que donnerait n’importe quel profane s’il était mis en présence de cette structure simple, mais puissante, dont les applications tant en génétique qu’en informatique sont légions.
La méthode de compression des fichiers au format Zip créée par l’américain David Huffman en 1952 est une application de la théorie des graphes. On peut également citer l’algorithme de recherche du plus court chemin proposé par le néerlandais Edgser Dijkstra, algorithme très employé dans le domaine des réseaux informatiques, où son utilité permet aux routeurs de déterminer le plus court chemin que doit emprunter un paquet pour atteindre sa destination.
Les graphes sont omniprésents en informatique. Leur origine est associée aux travaux du mathématicien Leonhard Euler en 1736, mais ils sont cependant très discrets. Combien sont-ils au courant de leur existence, alors qu’ils sont quotidiennement employés ?
Il n’est donc pas surprenant que le tout nouvel algorithme des chercheurs du MIT n’attire lui non plus l’attention, autant que le ferait la sortie d’un tout nouveau smartphone comme l’iPhone 5s par exemple.
Les travaux des chercheurs du MIT ont en effet porté sur la création d’un nouvel algorithme de parcours de graphe, dont l’évolution est quasi linéaire. Ils l’ont sobrement baptisé « KLOS algorithm », en l’honneur des chercheurs qui lui ont donné naissance (Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia et Aaron Sidford).
KLOS est présenté comme l’algorithme de parcours de graphe le plus abouti à l’heure actuelle. Il serait plus performant que les algorithmes de flot maximum (max flot) connus. KLOS sera présenté au cours du symposium sur les algorithmes discrets qui se tiendra à portland cette semaine.
Existe-t-il déjà des bibliothèques d’implémentation de KLOS ? Aucune à l’heure actuelle. Les développeurs sont appelés à être patients, car ça ne saurait tarder.
Source: Rapport de recherche PDF
Et vous ?
La méthode de compression des fichiers au format Zip créée par l’américain David Huffman en 1952 est une application de la théorie des graphes. On peut également citer l’algorithme de recherche du plus court chemin proposé par le néerlandais Edgser Dijkstra, algorithme très employé dans le domaine des réseaux informatiques, où son utilité permet aux routeurs de déterminer le plus court chemin que doit emprunter un paquet pour atteindre sa destination.
Les graphes sont omniprésents en informatique. Leur origine est associée aux travaux du mathématicien Leonhard Euler en 1736, mais ils sont cependant très discrets. Combien sont-ils au courant de leur existence, alors qu’ils sont quotidiennement employés ?
Il n’est donc pas surprenant que le tout nouvel algorithme des chercheurs du MIT n’attire lui non plus l’attention, autant que le ferait la sortie d’un tout nouveau smartphone comme l’iPhone 5s par exemple.
Les travaux des chercheurs du MIT ont en effet porté sur la création d’un nouvel algorithme de parcours de graphe, dont l’évolution est quasi linéaire. Ils l’ont sobrement baptisé « KLOS algorithm », en l’honneur des chercheurs qui lui ont donné naissance (Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia et Aaron Sidford).
KLOS est présenté comme l’algorithme de parcours de graphe le plus abouti à l’heure actuelle. Il serait plus performant que les algorithmes de flot maximum (max flot) connus. KLOS sera présenté au cours du symposium sur les algorithmes discrets qui se tiendra à portland cette semaine.
Existe-t-il déjà des bibliothèques d’implémentation de KLOS ? Aucune à l’heure actuelle. Les développeurs sont appelés à être patients, car ça ne saurait tarder.
Source: Rapport de recherche PDF
Et vous ?
-
KsassPeukMembre confirméL'important ici n'est clairement pas le parcours mais le flot maximum, or on a l'impression que c'est le parcours qui nous intéresse ici. Avec une structure de donnée basique, on peut déjà faire du linéaire en (n+m) pour le parcours.le 10/01/2014 à 14:31
-
hannibal.76Membre actifAttendre peut etre pas, je vais surtout remonter mes manches et implémenter ceci dans l'API GraphstreamAttendez-vous avec impatience des bibliothèques d'implémentation de KLOS ?le 10/01/2014 à 14:19
-
GLDavidExpert confirméBonjour
Je vois déjà une bonne implémentation de ces différents algorithmes dans mon domaine: la bioinformatique.
Savez-vous ce qu'est l'interactomique ? Il s'agit de la science d'étude des interactions entre les différentes protéines et les métabolites. Cette science utilise donc des graphes pour retranscrire le réseau d'interactions. Ces réseaux sont importants afin d'étudier toute la voie de signalisation d'une cellule, ce qui explique notamment des processus de pathologie comme le cancer. Mais également de mettre en évidence des voies de thérapies sur des cibles clairement identifiées par ce biais.
Ce qui émerge c'est l'inférence de réseaux: si une protéine est normalement produite, quel est l'impact dans la cascade des évènement si je la surexprime ? Ou si je la sous-exprime ?
Evidemment, des initiatives existent déjà pour encoder ces réseaux (XML et HUPO-PSI-MI notamment, plus RDF). Pour le jeu d'algorithmes comme la recherche de voisins ou le plus court chemoin, tout cela est intéressant pour gagner en performances.
A voir donc dans ce domaine.
@++le 10/01/2014 à 14:35 -
Peut-être une question stupide mais je me lance
A fortiori, KLOS devrait être applicable à des graphes orientés ?
Stephle 10/01/2014 à 15:26 -
srvremiMembre éclairéPour mes cours j'ai hâte de voir si ce sera implémentable par des élèves de niveau bac +3/+4.
@+
Rémile 10/01/2014 à 17:25 -
if_zenMembre avertiPetite question : est-ce que ce genre d'algorithme pourrait simplifier et améliorer les performances et résultats de l'algorithme du "voyageur de commerce" (cf. Wikipedia, ne pas confondre avec Dijkstra) consistant à trouver le plus court chemin sur un ensemble d'étapes pré-établi ?le 11/01/2014 à 19:36
-
razlockMembre à l'essai@if_zen je me posais la même question. De très bon algorithmes pour résoudre ce problème se basent sur les algos de flots, donc j'aurais tendance à dire qu'il y aura des répercussions sur pas mal de problèmes de ce genre ...
wait & seele 12/01/2014 à 16:30 -
Patriarch24Membre expérimentéJ'ai jeté un œil au papier, mais malheureusement mes compétences en mathématiques sont loin derrière moi et cela m'empêche de comprendre le tout (si tant est que mes compétences passées fussent suffisantes). Il faut être au point en algèbre...le 13/01/2014 à 9:12
-
aziasMembre éclairéPetite précision sur le nom "KLOS": ce ne sont pas les auteurs qui ont nommés cet algorithme KLOS, ils ne lui ont pas donné de nom (y aurait-il une raison de le faire d'ailleurs?). Alors c'est tout simplement nous tous qui utilisons KLOS par simplicité.
J'ai vaguement parcouru l’article ce week-end, j'ai été assez vite dépassé, je pense qu'il faut déjà connaître un peu les travaux antérieurs, en tout cas le vocabulaire, pour suivre.
Ils expliquent dans l’introduction qu'il s'agit d'une amélioration des algorithmes existant, leur permettant d'atteindre pour la première fois une complexité "quasi-linéaire" pour une résolution approchée du problème.
Le problème en question est un problème d'optimisation, celui du flot maximum: dans le graphe il y a une source et un puits et il s'agit de trouver comment répartir l'utilisation des arrêtes (chacune ayant sa limite de capacité) pour obtenir un flot maximum qui part de la source pour tomber dans le puits.le 13/01/2014 à 9:52 -
Teto45Membre habituéHeu... cette phrase a comme un problème... Pourquoi être patient si l'implémentation ne saurait tarder ?le 19/01/2014 à 9:25