Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!sun-barr!ccut!uecgw!coulomb!tanikuni
From: tanikuni@coulomb.cas.uec.junet (Kunihiro Taniguchi)
Newsgroups: comp.theory
Subject: maximize the euclidian norm
Message-ID: <947@uecgw.cs.uec.junet>
Date: 14 Dec 89 11:21:52 GMT
Sender: news@cs.uec.junet
Reply-To: tanikuni@cas.uec.ac.jp (Kunihiro Taniguchi)
Organization: University of Electro Communications, Chofu, Tokyo, JAPAN
Lines: 21


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