← All problems

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

4 years old · traced to

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 ∑x∈S∥y−x∥\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.

References

Status

  • Solved: Polina Barabanshchikova and Alexandr Polyanskii. Intersecting ellipses induced by a max-sum matching (Journal of Global Optimization, 2023) https://arxiv.org/abs/2212.14200

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

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.