Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.