Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/9214

Title: Some lower bounds for the complexity of the linear programming feasibility problem over the reals
Authors: GRIMSON, Rafael
Issue Date: 2009
Citation: JOURNAL OF COMPLEXITY, 25(1). p. 25-37
Abstract: We analyze the arithmetic complexity of the linear programming feasibility problem over the reals. For the case of polyhedra defined by 2n half-spaces in R-n we prove that the set l((2n,n)), of parameters describing nonempty polyhedra, has an exponential number of limiting hypersurfaces. From this geometric result we obtain, as a corollary, the existence of a constant c > I Such that, if dense or sparse representation is used to code polynomials, the length of any quantifier-free formula expressing the set l((2n,n)) is bounded from below by Omega(c(n)). Other related complexity results are stated; in particular, a lower bound for algebraic computation trees based oil the notion of limiting hypersurface is presented. (C) 2008 Elsevier Inc. All rights reserved.
Notes: [Grimson, Rafael; Kuijpers, Bart] Hasselt Univ, Theoret Comp Sci Grp, Diepenbeek, Belgium. [Grimson, Rafael; Kuijpers, Bart] Transnatl Univ Limburg, Limburg, Belgium. [Grimson, Rafael] Univ Buenos Aires, Dept Matemat, RA-1053 Buenos Aires, DF, Argentina.
URI: http://hdl.handle.net/1942/9214
DOI: 10.1016/j.jco.2008.07.002
ISI #: 000262046900003
ISSN: 0885-064X
Category: A1
Type: Journal Contribution
Validation: ecoom, 2010
Appears in Collections: Research publications

Files in This Item:

There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.