Please use this identifier to cite or link to this item:
Title: A lower bound for the complexity of linear optimization from a quantifier-elimination point of view
Authors: GRIMSON, Rafael 
Issue Date: 2007
Publisher: Dagstuhl
Source: BANK, Bernd & EGENHOFER, Max & KUIJPERS, Bart (Ed.) Dagstuhl Seminar Proceedings 07212: Constraint Databases, Geometric Elimination and Geographic Information Systems.
Abstract: We analyze the arithmetic complexity of the feasibility problem in linear optimization theory as a quantifier-elimination problem. For the case of polyhedra defined by 2n halfspaces in R^n we prove that, if dense representation is used to code polynomials, any quantifier-free formula expressing the set of parameters describing nonempty polyhedra has size Ω(4n ).
Document URI:
Link to publication:
Category: C1
Type: Proceedings Paper
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
07212.GrimsonRafael.ExtAbstract.1283.pdf168.31 kBAdobe PDFView/Open
Show full item record

Google ScholarTM


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