The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.6 / (1996))
A Deterministic Poly (LogLog N)-Time $N$-Processor Algorithm for Linear Programming in Fixed Dimension
Miklos Ajtai, Nimrod Megiddo,
Pages. 1171-1195
Abstract
Contents 1. Introduction
2. Preliminaries
3. Linear programming in the plane
4. The three-dimensional case
5. The general $d-$mensional case
5.1. Hyperplane queries
5.2. Locating the solution in a "small" simplex
5.3. Discarding constraints
6. The problem of processor allocation
Key words parallel computation, expander graph, parallel random-access machine (PRAM), linear programming.
Mathmatical Subject Classification 68U05, 90C05