I have a fully-connected graph $G=(V,E)$ with edge weights $w(v)\in\mathbb{R};v\in V$ and I need to find a spanning tree $T=(V_t\subseteq V,E_t\subseteq E)$ where the set of edge weights in the tree have as close as possible to equal separation. We quantify the notion of equal separation by minimizing the variance of difference between weights: $minimize: Var\left(\Delta(E_t)\right)$, where $Var$ is the variance function and $\Delta(E')=\{|w(e_1)-w(e_2)|, ..., |w(e_{n-1})-w(e_n)|\}$ where $e_i\in E'$ and $E'\subseteq E$ is a list of edges sorted by weight.
So an optimal solution to this problem will be an instance of $T$ such that $T$ is a spanning tree and $Var(\Delta(E_t))$ is the minimum over all possible spanning trees of $G$.
I have two ideas for this:
1) Pick a random starting node and perform a best-first spanning search, prioritizing the OPEN list for each $e'\in OPEN$ by $Var\left(\Delta(E_t \cup {e'})\right)$ where $E_t$ is the set of edges chosen so far in the search.
2) Find $n-1$ clusters of edges using a clustering algorithm such as k-means clustering based on $w(e)$ for all $e\in E$. Then (somehow) find a spanning tree that includes exactly one element from each of the $k$ cluster sets. (I think this might not work without doing something fancy to ensure that a spanning tree can actually be chosen from the sets.)
I coded up 1) and found that although it yields a fairly decent approximation it is sub-optimal, even if I take the best tree over all trees starting from each of the $n$ vertices... I have not yet tried 2).
This smells NP-hard... Is there an algorithm to compute a spanning tree with edge weights separated as equally as possible? (aside from brute-force?)
