Bipartite-coloring approximation conjecture for planar MAX-EMST-ratio

About 2 years old · traced to

Let P⊆R2P\subseteq\mathbb{R}^2 be a finite point set. A bipartite coloring is obtained by choosing a Euclidean minimum spanning tree of PP and partitioning P=R∪BP=R\cup B so that every edge of the chosen tree has endpoints of different colors. Bipartite-coloring approximation conjecture. For every point set in R2\mathbb{R}^2, the EMST-ratio for any bipartite coloring is a (1.5)(1.5)-approximation for the maximum EMST-ratio.

The source presents triangular chains as examples whose approximation proportion approaches 1.51.5, and notes that proving this conjecture would yield an O(nlog⁡n)O(n\log n)-time (1.5)(1.5)-approximation algorithm for the planar problem.

References

Primary source

Afrouz Jabal Ameli, Faezeh Motiei and Morteza Saghafian, “On the MST-ratio: Theoretical Bounds and Complexity of Finding the Maximum”, arXiv:2409.11079 (2025).

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.