On linear programming and matrix scaling over the algebraic numbers

Bahman Kalantari, M. R. Emamy-K

Research output: Contribution to journalArticle

3 Citations (Scopus)

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.

Original languageEnglish (US)
Pages (from-to)283-306
Number of pages24
JournalLinear Algebra and Its Applications
Volume262
Issue number1-3
StatePublished - Sep 1 1997

Fingerprint

Algebraic number
Linear programming
Scaling
Polynomials
Interior-point Algorithm
Models of Computation
Subroutines
Linear equations
Justify
Ellipsoid Method
Necessary
Rounding
System of Linear Equations
Polynomial-time Algorithm
Solvability
Polynomial time
Duality
Alternatives

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Cite this

@article{59a371d261a84ccf9793d35235908f92,
title = "On linear programming and matrix scaling over the algebraic numbers",
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.",
author = "Bahman Kalantari and Emamy-K, {M. R.}",
year = "1997",
month = "9",
day = "1",
language = "English (US)",
volume = "262",
pages = "283--306",
journal = "Linear Algebra and Its Applications",
issn = "0024-3795",
publisher = "Elsevier Inc.",
number = "1-3",

}

On linear programming and matrix scaling over the algebraic numbers. / Kalantari, Bahman; Emamy-K, M. R.

In: Linear Algebra and Its Applications, Vol. 262, No. 1-3, 01.09.1997, p. 283-306.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On linear programming and matrix scaling over the algebraic numbers

AU - Kalantari, Bahman

AU - Emamy-K, M. R.

PY - 1997/9/1

Y1 - 1997/9/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0038913455&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0038913455&partnerID=8YFLogxK

M3 - Article

VL - 262

SP - 283

EP - 306

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

IS - 1-3

ER -