線型計劃法에 의한 Khachiyan 方法의 응용연구 : State of the Art = The Application of Khachiyan's Algorithm for Linear Programming

다국어 초록 (Multilingual Abstract)

L.G. Khachiyan's algorithm for solving a system of strict (of open) linear inequalities with integral coefficients is described. This algorithm is bases on the construction of a sequence of ellipsoids R^n of decreasing n-dimensional volume and containing feasible region. The running time of the algorithm is polynomial in the number of bits of compu￣ter core meomry required to store the coefficients. It can be applied to solve linear programming problems in polynomially bounded time by the duality theorem of the linear programming problem. But it is difficult to use in solving practical problems. Because it requires the computation of a square roots, besides other arithmatic operations, it is impossible to o these computations exactly with absolute precision.