Exact algorithms for linear programming over algebraic extensions

Exact algorithms for linear programming over algebraic extensions

0.00 Avg rating0 Votes
Article ID: iaor20023733
Country: United States
Volume: 31
Issue: 4
Start Page Number: 459
End Page Number: 478
Publication Date: Dec 2001
Journal: Algorithmica
Authors:
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.

Reviews

Required fields are marked *. Your email address will not be published.