Suri's minimum Steiner star conjecture for max-sum matchings

From papers

Let SS be an even set of points in the plane, and let M\mathcal M be a max-sum matching of SS. Define t(S)t(S) as the minimum, over points yy in the plane, of xSyx\sum_{x\in S}\|y-x\|, the length of a minimum Steiner star on SS. Suri's conjecture. The minimum Steiner star satisfies

t(S)23  cost(M).t(S)\leq \frac{2}{\sqrt{3}}\;\operatorname{cost}(\mathcal M).

This conjecture arose in the study of communication networks and was the motivation for Fingerhut's conjecture. The paper's theorem proving Fingerhut's conjecture also confirms this bound.

Progress summary

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

Sources & referencesView supporting material

Primary source

Polina Barabanshchikova and Alexandr Polyanskii, “Intersecting ellipses induced by a max-sum matching”, arXiv:2212.14200 (2023).

Solutions 0

No solutions have been posted yet.