A continuous method for computing bounds in integer quadratic optimization problems |
| |
Authors: | A Kamath N Karmarkar |
| |
Institution: | (1) AT & T Bell Laboratories, 07974 Murray Hill, NJ, U.S.A. |
| |
Abstract: | In the graph partitioning problem, as in other NP-hard problems, the problem of proving the existence of a cut of given size is easy and can be accomplished by exhibiting a solution with the correct value. On the other hand proving the non-existence of a cut better than a given value is very difficult. We consider the problem of maximizing a quadratic function x
T
Q
x where Q is an n × n real symmetric matrix with x an n-dimensional vector constrained to be an element of {–1, 1}
n
. We had proposed a technique for obtaining upper bounds on solutions to the problem using a continuous approach in 4]. In this paper, we extend this method by using techniques of differential geometry. |
| |
Keywords: | Bounds interior-point integer quadratic optimization Riemannian geometry |
本文献已被 SpringerLink 等数据库收录! |
|