Dissimilarités de Robinson (algorithmes de reconnaissance et d'approximation)

Une distance ou plus généralement une dissimilarité d définie sur un ensemble X de n éléments, est dite Robisonienne s'il existe un ordre total = max{d(x,y), d(y,z)}. Un tel ordre est dit compatible avec d. Dans la première partie, nous présentons deux algorithmes de complexité O(n^3) et O(n^2 log n) pour la reconnaissance des dissimilarités de Robinson. Ces algorithmes permettent de coder de façon compacte l'ensemble des ordres compatibles via les PQ-arbres. La deuxième partie concerne l'approximation en norme l_{\infty} d'une dissimilarité de Robinson. Plus formellement, on veut trouver une dissimilarité de Robinson d_R qui miminise l'erreur :||d-d_R||_{\infty}=\max_{x,y\in X} {|d(x,y)-d_(x,y)|}. Nous montrons que ce problème est NP-difficile. Nous présentons également un algorithme d'approximation avec un facteur 16 pour ce problème, ce qui constitue le résultat principal de cette thèseAIX-MARSEILLE2-BU Sci.Luminy (130552106) / SudocSudocFranceF