aussois_header.png

Tropical medians by transportation
Andrei Comaneci, Michael Joswig  1@  
1 : TU Berlin

The classical Fermat-Weber problem can be studied for arbitrary distance functions.
The goal is to find a point (which is often not unique) which minimizes the average distance to a given finite set of points.
We show that a certain asymmetric tropical Fermat-Weber problem can be reduced to a transportation problem and thus be solved in strongly polynomial time.

This result can be used to construct consensus trees in phylogenetics.
The resulting trees are guaranteed to satisfy several desirable properties.


Personnes connectées : 2 Vie privée | Accessibilité
Chargement...