Polynomial algorithms for linear programming over the algebraic numbers
type: Item
instance of: scholarly article
title: Polynomial algorithms for linear programming over the algebraic numbers
zbMATH Open document ID: 0855.68039
DOI: 10.1007/BF01188714
published in: Algorithmica
publication date: 1995-02-28T00:00:00Z
review text: Linear programming (LP) is the problem of maximizing \(cx\) \((c\), a fixed \(n\)-vector), subject to \(Ax \Leftarrow b\) \((A\), a fixed \(m\) by \(n\) matrix and \(b\) a fixed \(m\)-vector). The dimension of a problem instance is the total number of entries in the vectors and matrices that define the instance (above: \(mn + n + m)\). The size of a problem instance is the total number of bits needed to encode these entries in binary notation. An algorithm for LP is said to be polynomial time, if its running time is bounded by a polynomial in the dimension plus the size of the input instance. In 1979, Khachiyan solved a long-standing open problem by presenting a polynomial-time algorithm for rational LPs (i.e., when all entries of the LP instance are rational numbers). Indeed, both Khachiyan's ellipsoid method and Karmarker's interior-point method solve rational LPs in polynomial time (in the above sense). Unfortunately, these results do not extend to LPs with arbitrary real numbers as coefficients. One problem is that there seems to be no useful concept of size for (nonrational) real numbers. In this paper the author derive complexity bounds for LPs with coefficients in the set of algebraic numbers. They utilize results from algebra and number theory to define a useful measure of size for input coefficients. Then they present an algorithm, fashioned after the ellipsoid algorithm of Khachiyan, that runs in polynomial time in the dimension plus the degree of the extension defined by the input coefficients plus the size of the input instance.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W10
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 713573
zbMATH Keywords: algebraic numbers
zbMATH Keywords: computational complexity
zbMATH Keywords: polynomial-time algorithms
zbMATH Keywords: linear programming
zbMATH Keywords: ellipsoid method
author: Ilan Adler
author: Peter A. Beling
reviewed by: Giora Slutzki
MaRDI profile type: Publication
cites work: Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices
cites work: On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
cites work: Q5661948
cites work: A new polynomial-time algorithm for linear programming
cites work: Q3050157
cites work: Towards a Genuinely Polynomial Algorithm for Linear Programming
cites work: Linear Programming in Linear Time When the Dimension Is Fixed
cites work: Q3973277
cites work: Q3138915
cites work: Q4739657
cites work: Q3813882
cites work: A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
cites work: Complexity of linear programming
full work available at URL: https://doi.org/10.1007/bf01188714
OpenAlex ID: W2024997126
Recommended article: Q3796957
Recommended article: Polynomial affine algorithms for linear programming
Recommended article: Q4197641
Recommended article: Q3050157
Recommended article: Q4733661
Recommended article: Q3028715
Recommended article: Towards a Genuinely Polynomial Algorithm for Linear Programming
Recommended article: Exact algorithms for linear programming over algebraic extensions
Recommended article: Q4540814
description: scientific article; zbMATH DE number 713573