본문 바로가기
KERD
논문KCI 등재

Integer programming in an algebraic computation model

Valentin E. Brimkov|Stefan S. Dantchev
장전수학회 (Jangjeon Mathematical Society)|2006.07|Advanced Studies in Contemporary Mathematics|제13권 제1호|pp. 5-20

1

조회

0

다운로드

0

인용

0

참고문헌

주제분류수학

초록

Abstract

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).

참고문헌 (18)

  1. Ben-Or, M., "Lower bounds for algebraic computation tree", the 15th ACM STOC, pp.80~86 (1983)
  2. Blum, L., "Complexity and Real Computation" (1995), Berlin Heidelberg New York: Springer-Verlag
  3. Blum, L., "On a Theory of Computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines", Bull. Amer. Math. Soc., 21, pp.1~46 (1989)
  4. Brimkov, V.E., "Real data { integer solution problems within the Blum-Shub-Smale computational model", J. of Complexity, 13, pp.279~300 (1997)
  5. Brimkov, V.E., "An alternative to Ben-Or's lower bound for the knapsack problem complexity", Applied Mathematics Letters, 15, pp.187~191 (2002)
  6. Burgisser, P., "Algebraic Complexity Theory" (1997), Heidelberg: Springer-Verlag
  7. Frank, A., "An application of simultaneous diophantine approximation in combinatorial optimization", Combinatorica, 7(1), pp.49~65 (1987)
  8. Hastad, J., "polynomial time algorithms for nding integer relations among real numbers", SIAM J. Comput., 18, pp.859~881 (1989)
  9. Haussler, D., "Epsilon-nets and simplex range queries", Discrete Computational Geometry, 2, pp.127~151 (1987)
  10. Kannan, R., "Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix", SIAM J. Comput., 8, pp.499~507 (1979)
  11. H.W. Lenstra Jr, "Integer programming with a xed number of variables", Math. Oper. Res., 8, pp.538~548 (1983)
  12. Lenstra, A.K., "Factoring polynomials with rational coecients", Math. Ann., 261, pp.515~534 (1982)
  13. Megiddo, N., "Linear Programming in linear time when the dimension is fixed", J. of ACM, 31(1), pp.114~127 (1984)
  14. Meiser, S., "Point Location in arrangements of hyperplanes", Information and Computation, 106, pp.286~303 (1993)
  15. Heide, F. Meyer Auf Der, "A polynomial linear search algorithm for the n-dimensional knapsack problem", J. of ACM, 31(3), pp.668~676 (1984)
  16. Heide, F. Meyer auf der, "Fast algorithms for n-dimensional restrictions of hard problems", J. ACM, 35, pp.740~747 (1998)
  17. Schrijver, A., "Theory of Linear and Integer Programming" (1986), Chichester New York Brisbane Toronto Singapore: Wiley
  18. Smale, S, "Some remarks on the foundations of numerical analysis", SIAM Rev., 32(2), pp.211~220 (1990)

관련 논문AI추천

Implicitization of rational curves and polynomial surfacesJian-ping Yu, Yong-li Sun대한수학회 · 대한수학회보2007 · 제44권 제1호A successive quadratic programming algorithm for SDP relaxation of the binary quadratic programingSanyang Liu, Xuewen Mu, Yaling Zhang대한수학회 · 대한수학회보2005 · 제42권 제4호Rank-preserving operators of nonnegative integer matrices강경태, 송석준, 전영배대한수학회 · 대한수학회논문집2005 · 제20권 제4호On reduction of interval decision-making problemsD. V. Dolgy장전수학회 · Advanced Studies in Contemporary Mathematics2023 · 제33권 제1호Maximal column rank preservers of integer matrices강경태, 송석준대한수학회 · 대한수학회논문집2007 · 제22권 제2호Factor Rank Comparisons of Matrices over Two Related Semirings송석준대한수학회 · 대한수학회논문집2006 · 제21권 제2호

이 간행물의 다른 논문 (12건)

On a nonlinear system of functional difference equations with nonlinear complicated mixed maximaT. K. Yuldashevpp. 1-4On a class of conjectures equivalent to the strong Goldbach's conjecturePeter Vassilevpp. 21-26A linear operator and associated families of meromorphically multivalent functions of order aM. K. Aouf, H. M. Srivastavapp. 27-56A refinement of Carleman's inequalityJ. Cao, D.-W. Niu, F. Qipp. 57-62Existence of integral manifolds for impulsive integro-differential equationsGani Tr. Stamovpp. 63-68
원문 보기