maes@prl.philips.nl (Maurice Maes) (12/05/90)
We need help, e.g. references, on the following problem.
Given a set of vectors {v1, v2, ..., vk} in n-dimensional
Euclidean space. Determine numbers (signs) e1, e2, ..., ek in {-1, 1},
such that
|| e1*v1 + e2*v2 + ... + ek*vk ||
is minimum.
(Here ||v|| denotes the length of the vector v, of course.)
It is easily seen that PARTITION (Garey & Johnson, problem [SP12])
is a special case of this problem, so it is NP-complete.
PARTITION however, is solvable in pseudo-polynomial time by
dynamic programming, so we wonder if there are any useful
algorithms known for the problem above.
Please mail or post,
Thanks.
Maurice Maesxanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (12/17/90)
maes@prl.philips.nl (Maurice Maes) writes: >We need help, e.g. references, on the following problem. >Given a set of vectors {v1, v2, ..., vk} in n-dimensional >Euclidean space. Determine numbers (signs) e1, e2, ..., ek in {-1, 1}, >such that > || e1*v1 + e2*v2 + ... + ek*vk || >is minimum. >(Here ||v|| denotes the length of the vector v, of course.) >It is easily seen that PARTITION (Garey & Johnson, problem [SP12]) >is a special case of this problem, so it is NP-complete. >PARTITION however, is solvable in pseudo-polynomial time by >dynamic programming, so we wonder if there are any useful >algorithms known for the problem above. Excuse my limited familiarity with the vocabulary here, but if "solvable" here means "approximately solvable", then a perturbational approach might be fruitful. Explicitly, presume k is a power of two, and assign v1...vk to the leaves of a complete binary tree (if k is not a power of two, assign vectors to the leaves "from left to right" until you run out of vectors, then move vectors at the right up the tree pruning leaves until there are no empty leaf nodes). Process from leaf to root, making one of the sign choices at each node that minimizes the summed length of the two vectors subordinate to this level (for orthogonal vectors, choose at random). At the root you will have a candidate minimum summed vector length and associate set of sign assignments. Now do random permutations of the vector to leaf assignments and repeat the calculation of new candidates until some stopping criterion is met: 1) Little (no) improvement has been recently seen; or 2) the alloted processing time is exhausted. One may either completely reassign the vector to leaf matching at each iteration, or just swap two randomly chosen assignments; the latter justifies my use of "perturbational", above. In practice, a mix of these two methods might work better than either alone. The superior candidate minimum summed vector length and associated assignment of signs at the point the stopping criterion is met is in some sense an approximation of a fully worked out (exponential time) solution. I've no idea how effective this would be in practice, but it is one possible approach worth considering. Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>