Fingerhut's max-sum matching conjecture

Let SS be an even set of points in the plane, and let {aibi:i=1,,n}\{a_ib_i:i=1,\dots,n\} be a max-sum matching of SS, where S=2n|S|=2n. A point oo is required to satisfy, for every matched pair, the sum of its distances to the pair's endpoints. Fingerhut's conjecture. There exists a point oo in the plane such that

aio+bio23aibifor all i=1,,n.\|a_i-o\|+\|b_i-o\|\leq \frac{2}{\sqrt 3}\|a_i-b_i\|\qquad\text{for all }i=1,\dots,n.

The factor 2/32/\sqrt 3 is optimal, and the conjecture was introduced by Andy Fingerhut in connection with minimum Steiner stars; it was previously known with weaker factors and is proved in this paper.

Sources & referencesView supporting material

Primary 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.