Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!wuarchive!mit-eddie!bloom-beacon!eru!hagbard!sunic!mcsun!hp4nl!phigate!prle!prles2!prl.philips.nl!maes
From: maes@prl.philips.nl (Maurice Maes)
Newsgroups: comp.theory
Subject: Minimizing sum of vectors; PARTITION; Help needed!
Message-ID: <2396@prles2.prl.philips.nl>
Date: 5 Dec 90 10:02:39 GMT
References: <10048@ucrmath.ucr.edu>
Sender: news@prles2.prl.philips.nl
Organization: Philips Research Laboratories Eindhoven, the Netherlands
Lines: 21

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 Maes


Brought to you by Super Global Mega Corp .com