IIIT Hyderabad Publications |
|||||||||
|
NP Hard Problems: Many Linear Objective Function Optimization ProblemAuthors: Garimella Ramamurthy Date: 2016-05-10 Report no: IIIT/TR/2016/23 AbstractIt is well known that the problem of determining the maximum cut in an undirected graph is an NP Complete Problem. The author proved that computing the global minimum anti-stable state of a Hopfield neural network ( i.e. the global minimum of associated energy function ) is equivalent to computing the maximum cut in the associated graph ( which is equivalent to computing the corner of hypercube at which the global minimum of quadratic form is attained ). In this research paper, it is shown that computing the global minimum of quadratic form associated with a positive definite symmetric matrix can be formulated as minimization of many linear objective functions over the unit hypercube. Full report: pdf Centre for Security, Theory and Algorithms |
||||||||
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved. |