IIIT Hyderabad Publications
NP Hard Problems: Many Linear Objective Function Optimization Problem
Authors: Garimella Ramamurthy
Report no: IIIT/TR/2016/23
It 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.