• 1
  • 2
  • 3
  • 4
IPM
30
YEARS OLD

“School of Mathematics”

Paper   IPM / M / 469
   School of Mathematics
  Title: On linear programming and matrix scaling over the algebraic numbers
  Author(s):
1 . B. Kalantari
2 . M. R. Emamy-K
  Status: Published
  Journal: Linear Algebra Appl.
  Vol.: 262
  Year: 1997
  Pages: 283-306
  Supported by: IPM
  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
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
scroll left or right