“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
polynomial-time 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 constraint-matrix 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 polynomial-time
interior-point 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
interior-point algorithms under an input model; and give an
alternative method to the traditional duality-based approach for
the conversion of a general linear programming problem into a
feasibility problem.
Download TeX format |
|||||
| back to top | |||||
