Vertex arrangement on the unit sphere

Question

The problem is how can I solve a following in polynomial time? There is a graph $G$ with $n$ vertices, and the goal is to find an arrangement of its vertices on an $n$-dimensional unit-sphere so as to maximize the sum of the angles made by the edges. Angles always should be in the range $[0; \pi]$. The problem is I can't find any similar well-known problem, which is can be solvable in polynomial time. I will appreciate any help. Thanks!

Answer 1

I wouldn't expect this to have a closed-form solution; if it doesn't, the question of solving it in polynomial time doesn't arise.

If the number of vertices were large compared to the number of dimensions, I'd expect it to be a difficult global optimization problem with lots of local maxima. However, since you have as many vertices as dimensions, there's room for the vertices to get out of each other's way, and you may be able to find the global maximum, or at least a satisfactory local maximum, by starting out with the $n$ vertices far apart, for instance at the vertices of a regular $(n+1)$-simplex (with $2$ vertices of the simplex left unoccupied, assuming that by "$n$-dimensional unit sphere" you mean the unit $n$-sphere $S^n$ in $n+1$ dimensions), and then applying your favourite global optimization algorithm. If I'm right, then you should be able to get by with a simple gradient search, similar to the one I described at Gradient descent with constraints, but simpler since you don't have orthogonality constraints.