Exact Algorithms for Linear Programming over Algebraic Extensions |
| |
Authors: | Beling |
| |
Affiliation: | (1) Department of Systems Engineering, University of Virginia, Charlottesville, VA 22903, USA. beling@ virginia.edu., US |
| |
Abstract: | Abstract. We study the computational complexity of linear programs with coefficients that are real algebraic numbers under a Turing
machine model of computation. After reviewing a method for exact representation of algebraic numbers under the Turing model,
we show that the fundamental tasks of comparison and arithmetic can be performed in polynomial time. Our technique for establishing
polynomial-time algorithms for comparison and arithmetic is distinct from the usual resultant-based approaches, and has the
advantage that it provides a natural framework for analysis of the complexity of computational tasks, such as Gaussian elimination,
that involve a sequence of arithmetic operations. Our main contribution is to show that a variant of the ellipsoid method
can be used to solve linear programming in time polynomial in the encoding size of the problem coefficients and the degree
of any algebraic extension that contains those coefficients. |
| |
Keywords: | , Linear programming, Algebraic numbers, Computational complexity, Symbolic computation, Ellipsoid method, Polynomial-time,,,,,algorithms, |
本文献已被 SpringerLink 等数据库收录! |
|