Ivanov–Tuzhilin half-perimeter formula for minimal fillings

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,π)=12xMρ(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)=minGmaxπ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.

Sources & referencesView supporting material

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.