[comp.theory] maximize the euclidian norm

tanikuni@coulomb.cas.uec.junet (Kunihiro Taniguchi) (12/14/89)

I am working on Neural Net. The following optimization problem:

"For any given n x n matrix A, maximize the euclidian norm of
Ab over any b in {-1,1}^n. "

is crucial in the analysis and I need to know its computational
complexity for the ordinary computing system. Is this NP complete?
Does anyone know any good epsilon approximate algorithm? In addition, 
what this problem is related  computationally with

"For any given n x n square matrix A, to find the minimal nonzero
norm over the integer lattice made from the columns of A."

,for which I have a reference for the polynomial epsilon approximate 
algorithm.


						Kunihiro Taniguchi
			University of Electro Communications,Tokyo,Japan
				E-mail Address: tanikuni@cas.uec.ac.jp