Des chercheurs du MIT créent KLOS
Un puissant algorithme de parcours de graphes non orientés

Le , 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 ?

Attendez-vous avec impatience des bibliothèques d'implémentation de KLOS ?


Vous avez aimé cette actualité ? Alors partagez-la avec vos amis en cliquant sur les boutons ci-dessous :


 Poster une réponse

Avatar de hannibal.76 hannibal.76 - Membre actif https://www.developpez.com
le 10/01/2014 à 14:19
Attendez-vous avec impatience des bibliothèques d'implémentation de KLOS ?

Attendre peut etre pas, je vais surtout remonter mes manches et implémenter ceci dans l'API Graphstream
Avatar de KsassPeuk KsassPeuk - Membre actif https://www.developpez.com
le 10/01/2014 à 14:31
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.
Avatar de GLDavid GLDavid - Membre expert https://www.developpez.com
le 10/01/2014 à 14:35
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.

@++
Avatar de - https://www.developpez.com
le 10/01/2014 à 15:26
Peut-être une question stupide mais je me lance

A fortiori, KLOS devrait être applicable à des graphes orientés ?

Steph
Avatar de srvremi srvremi - Membre confirmé https://www.developpez.com
le 10/01/2014 à 17:25
Pour mes cours j'ai hâte de voir si ce sera implémentable par des élèves de niveau bac +3/+4.

@+
Rémi
Avatar de if_zen if_zen - Membre averti https://www.developpez.com
le 11/01/2014 à 19:36
Petite 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 ?
Avatar de razlock razlock - Membre à l'essai https://www.developpez.com
le 12/01/2014 à 16:30
@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 & see
Avatar de Patriarch24 Patriarch24 - Membre expérimenté https://www.developpez.com
le 13/01/2014 à 9:12
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...
Avatar de azias azias - Membre éclairé https://www.developpez.com
le 13/01/2014 à 9:52
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.
Avatar de Teto45 Teto45 - Membre habitué https://www.developpez.com
le 19/01/2014 à 9:25
Citation Envoyé par Cedric Chevalier  Voir le message
... Les développeurs sont appelés à être patients, car ça ne saurait tarder.

Heu... cette phrase a comme un problème... Pourquoi être patient si l'implémentation ne saurait tarder ?
Offres d'emploi IT
Architecte sécurité des systèmes d'information embarqués H/F
Safran - Ile de France - 100 rue de Paris 91300 MASSY
Consultant sap finance/controlling H/F
Safran - Ile de France - Vélizy-Villacoublay (78140)
Expert décisionnel business intelligence H/F
Safran - Ile de France - Évry (91090)

Voir plus d'offres Voir la carte des offres IT
Contacter le responsable de la rubrique Accueil