Rubinstein–Weng–Wormald linear-error conjecture for minimum-topology approximate Steiner trees

Let an ε\varepsilon-approximate Steiner tree be a tree whose angles at Steiner points lie in [2π/3ε,2π/3+ε][2\pi/3-\varepsilon,2\pi/3+\varepsilon]. For d2d\geqslant 2, let Aεd(n)\overline{{\mathcal A}}_\varepsilon^d(n) be the subset of full ε\varepsilon-approximate Steiner trees on nn terminals in Rd\mathbb R^d whose terminals have a minimum Steiner tree with the same topology. If

Fd(ε,n)=sup{L(T)L(S(T))L(S(T)):TAεd(n)},\overline{F}_d(\varepsilon,n)=\sup\left\{\frac{L(T)-L(S(T))}{L(S(T))}:T\in\overline{{\mathcal A}}_\varepsilon^d(n)\right\},

where S(T)S(T) is the shortest tree with the topology of TT, then Rubinstein–Weng–Wormald's conjecture. For any d2d\geqslant 2 there exist ε0>0\varepsilon_0>0 and Cd>0C_d>0 such that for all ε(0,ε0)\varepsilon\in(0,\varepsilon_0) and nNn\in\mathbb N,

Fd(ε,n)<Cdε.\overline{F}_d(\varepsilon,n)<C_d\varepsilon.

The conjecture gives the same uniform linear error bound when the prescribed topology is realized by a minimum Steiner tree; the supplied text states that this case remains open.

Sources & referencesView supporting material

Primary source

Charl Ras, Konrad J. Swanepoel and Doreen Thomas, “Approximate Euclidean Steiner Trees”, arXiv:1605.01172 (2016).

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.