Ivanov–Tuzhilin half-perimeter formula for minimal fillings

About 14 years old · traced to

Let M=(M,ρ){\mathcal M}=(M,\rho) be a finite metric space. For a tree GG connecting MM, let O(M,G){\mathcal O}(M,G) be the set of tours of MM with respect to GG, and for each π∈O(M,G)\pi\in{\mathcal O}(M,G) define the half-perimeter by

p(M,G,π)=12∑x∈Mρ(x,π(x)).p({\mathcal M},G,\pi)=\frac{1}{2}\sum_{x\in M}\rho\bigl(x,\pi(x)\bigr).

Let mf⁡(M)\operatorname{mf}({\mathcal M}) denote the weight of a minimal filling. Ivanov–Tuzhilin hypothesis. For an arbitrary metric space M=(M,ρ){\mathcal M}=(M,\rho),

mf⁡(M)=min⁡Gmax⁡π∈O(M,G)p(M,G,π),\operatorname{mf}({\mathcal M})=\min_G\max_{\pi\in{\mathcal O}(M,G)}p({\mathcal M},G,\pi),

where the minimum is taken over all binary trees GG connecting MM. The formula proposes a tour-based characterization of minimal filling weight; the source attributes it to A. Ivanov and A. Tuzhilin and gives no resolution.

References

Primary source

A. O. Ivanov and A. A. Tuzhilin, “Optimal Networks”, arXiv:1210.6228 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.