首页 | 本学科首页   官方微博 | 高级检索  
文章检索
  按 检索   检索词:      
出版年份:   被引次数:   他引次数: 提示:输入*表示无穷大
  收费全文   3篇
  数学   3篇
  1992年   1篇
  1991年   1篇
  1984年   1篇
排序方式: 共有3条查询结果,搜索用时 46 毫秒
1
1.
A new polynomial-time algorithm for linear programming   总被引:116,自引:0,他引:116  
We present a new polynomial-time algorithm for linear programming. In the worst case, the algorithm requiresO(n 3.5 L) arithmetic operations onO(L) bit numbers, wheren is the number of variables andL is the number of bits in the input. The running-time of this algorithm is better than the ellipsoid algorithm by a factor ofO(n 2.5). We prove that given a polytopeP and a strictly interior point a εP, there is a projective transformation of the space that mapsP, a toP′, a′ having the following property. The ratio of the radius of the smallest sphere with center a′, containingP′ to the radius of the largest sphere with center a′ contained inP′ isO(n). The algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in polynomial time. This is a substantially revised version of the paper presented at the Symposium on Theory of Computing, Washington D. C., April 1984.  相似文献
2.
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.  相似文献
3.
1
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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