http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
Integer programming in an algebraic computation model
Valentin E. Brimkov,Stefan S. Dantchev 장전수학회 2006 Advanced Studies in Contemporary Mathematics Vol.13 No.1
We study the algebraic complexity of the integerlinear programming problem (ILPR ) Given a matrix A 2 Rm n and vectors b 2 Rm,d 2 Rn,decide whether there is x 2 Zn such that Ax b,where 0 x d. We present an O (m logjjdjj) algorithm for ILPR , when the value of the problem dimension n is fixed.As a corollary,we obtain under the same restriction a tight algebraic complexity bound for the knapsack problem (KPR ) Givena 2 Rn+ ,decide whether there is x 2 Zn+ such that aTx = 1. We also propose an Omn5 logn (n + logjjdjj) depth algebraic computation tree for ILPR ,for every m and n (i.e.in a model which is non-uniformw ith respect to them).