Improved Lower Bounds on Tree Covers

Yu Chen, Shengtang Huang, Zihan Tan +1

A tree cover of an $n$-point metric space is a collection of $k$ trees such that every pairwise distance is approximately preserved in at least one tree. For fixed $k$, the best kn…