I'm pretty new to programming and computer science, but I was wondering if there was any good way to approach the following problem: For a set of 2n points (not necessarily unique) in R^k (assume each entry is positive), I want an algorithm which will partition the set into n pairs such that the average Euclidean distance squared is minimized. EDIT: Edited for clarity.
Minimizing Average Pairwise Squared Euclidean Norm
algorithms
You are looking for a minimum weight perfect matching in a complete weighted undirected graph. Your 2n points are the vertices, and each pair of vertices has an undirected edge between them with weight equal to the Euclidean distance between the points.The Blossom Algorithm can solve this problem. According to (Kolmogorov, 2009) linked from the Wikipedia page, the best known complexity bound is O(|V||E| + |V| log |V|), which in your case would be O(n^3) because it's a complete graph.Reference: Kolmogorov, 2009. Blossom V: a new implementation of a minimum cost perfect matching algorithm. Mathematical Programming Computation, vol. 1, issue 1, pp. 43-67.