Optimality of the square lattice among Steiner networks
Optimality of the square lattice among Steiner networks
Let the cities be the points in the plane, and consider a Steiner network on this square-grid configuration. Its normalized length is its total network length per unit area, and its stretch is the maximum ratio between network distance and Euclidean distance for pairs of cities. Square-grid Steiner-network optimality conjecture. If a Steiner network on the square-grid configuration has stretch at most , then its normalized length is at least . The usual square-lattice network has normalized length and stretch , so the conjecture asserts its optimality among Steiner networks with stretch at most .
Sources & referencesView supporting material
Primary source
David Aldous and Tamar Lando, “The Stretch - Length Tradeoff in Geometric Networks: Average Case and Worst Case Study”, arXiv:1404.2653 (2014).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.