“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 469  


Abstract:  
Adler and Beling considered the linear programming problem over
the real algebraic numbers. They obtained the necessary bounds in
terms of a notion of size and dimension needed to justify its
polynomialtime solvability, using the ellipsoid method and under
some models of computation. Based on a better notion of size than
that used by Adler and Beling, we first reduce the feasibility
problem in linear programming to some canonical problems
preserving its size and its constraintmatrix dimensions. For
these canonical problems as well as for the matrix scaling
problem, shown to be a more general problem than linear
programming, we obtain the necessary bounds; demonstrate simple
rounding schemes; justify the applicability of two polynomialtime
interiorpoint algorithms under some models of computation;
describe a method for solving a system of linear equations over
the algebraic numbers which is a subroutine within these
interiorpoint algorithms under an input model; and give an
alternative method to the traditional dualitybased approach for
the conversion of a general linear programming problem into a
feasibility problem.
Download TeX format 

back to top 