Fixed-dimensional hardness conjecture for MAX-EMST-ratio
Fixed-dimensional hardness conjecture for MAX-EMST-ratio
For a point set in Euclidean space, the -MAX-EMST-ratio problem restricts the input to dimensions. Fixed-dimensional hardness conjecture. The -MAX-EMST-ratio problem for is NP-hard.
The unrestricted MAX-EMST-ratio problem is established to be NP-hard, while hardness in the specific practical dimensions and remains conjectural.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.