Document Server@UHasselt >
Research >
Research publications >

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

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
Citation: 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 ).
URI: http://hdl.handle.net/1942/7969
Link to publication: http://drops.dagstuhl.de/opus/volltexte/2007/1283/pdf/07212.GrimsonRafael.ExtAbstract.1283.pdf
ISSN: 1862-4405
Category: C1
Type: Proceedings Paper
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A168.31 kBAdobe PDF

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