Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/9214
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | GRIMSON, Rafael | - |
dc.contributor.author | KUIJPERS, Bart | - |
dc.date.accessioned | 2009-01-29T15:51:06Z | - |
dc.date.issued | 2009 | - |
dc.identifier.citation | JOURNAL OF COMPLEXITY, 25(1). p. 25-37 | - |
dc.identifier.issn | 0885-064X | - |
dc.identifier.uri | http://hdl.handle.net/1942/9214 | - |
dc.description.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. | - |
dc.language.iso | en | - |
dc.publisher | ACADEMIC PRESS INC ELSEVIER SCIENCE | - |
dc.subject.other | Lower bounds; Linear programming; Algebraic complexity; Limiting hypersurface; Elimination theory | - |
dc.title | Some lower bounds for the complexity of the linear programming feasibility problem over the reals | - |
dc.type | Journal Contribution | - |
dc.identifier.epage | 37 | - |
dc.identifier.issue | 1 | - |
dc.identifier.spage | 25 | - |
dc.identifier.volume | 25 | - |
local.format.pages | 13 | - |
local.bibliographicCitation.jcat | A1 | - |
dc.description.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. | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
dc.bibliographicCitation.oldjcat | A1 | - |
dc.identifier.doi | 10.1016/j.jco.2008.07.002 | - |
dc.identifier.isi | 000262046900003 | - |
item.accessRights | Closed Access | - |
item.contributor | GRIMSON, Rafael | - |
item.contributor | KUIJPERS, Bart | - |
item.fulltext | No Fulltext | - |
item.fullcitation | GRIMSON, Rafael & KUIJPERS, Bart (2009) Some lower bounds for the complexity of the linear programming feasibility problem over the reals. In: JOURNAL OF COMPLEXITY, 25(1). p. 25-37. | - |
item.validation | ecoom 2010 | - |
crisitem.journal.issn | 0885-064X | - |
crisitem.journal.eissn | 1090-2708 | - |
Appears in Collections: | Research publications |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.