首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号