k车服务问题与竞争算法

本文以 k 车服务问题为线索,介绍最优化领域中出现的越来越热的一个新方向——局内问题与竞争算法.     

REMARKS ON THE CONVERGENCE OF ROSEN''''S GRADIENT PROJECTION METHOD

The convergence of Rosen's gradient projection method is a long-standing problem in nonlinearprogramming.Recently,Zhang proved that it is convergent in the 3-dimensional space;Du andZhang proved its convergence in n-dimensional space under a restriction on a paramater in Rosen'smethod.In this paper,we propose a linearly algebraic conjecture which can yield the convergence ofRosen's method without the restriction.By verifying this conjecture for some special cases,we provethat Rosen's method is convergent in 4-dimensional space.     

NOTES ON POLYNOMIAL LEVELABILITY

We consider the polynomial levelability with respect to approximation algorithms (PLAA).A set A is PLAA if given any approximation algorithm a for A and a polynomial p,there are another approximation algorithm β for A and a polynomial q such that for infinitely many inputs x,a accepts x but has ruuning time greater than p(|x|) and β accepts x within time q(|x|).In this paper,an algorithm a is called an approximation algorithm for A if the symmetric difference A△L(a) is sparse,where L(a) is the set of strings recegnized by a.We prove that all natural NP-complete sets are PLAA unless P=NP and all EXP-complete sets are PLAA.     

谈谈斯坦纳树

谈谈斯坦纳树堵丁柱中国科学院应用数学研究所１０００８０）１费尔马的问题最短网络是项历史悠久的数学课题．它的历史可以追溯到费尔马．１６４０年，费尔马提出如下问题：于平面上给出Ａ，Ｂ，Ｃ三点，求一点Ｓ使距离和ＳＡ＋ＳＢ＋ＳＣ达到最小．该问题引起了许多人的...