On the Metric Distortion of the Minimum Spanning Tree Problem

Kian Ghassemi, Masoud Seddighin, Saeed Seddighin

We study the metric distortion of the minimum spanning tree (MST) problem when numerical edge weights are unavailable and each vertex reports only a ranking of the other vertices i…