DagSemProc.07212.3.pdf
- Filesize: 168 kB
- 6 pages
Document
A lower bound for the complexity of linear optimization from a quantifier-elimination point of view
Author
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 7212
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2007-12-17
Cite As Get BibTex
Rafael Grimson. A lower bound for the complexity of linear optimization from a quantifier-elimination point of view. In Constraint Databases, Geometric Elimination and Geographic Information Systems. Dagstuhl Seminar Proceedings, Volume 7212, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
https://doi.org/10.4230/DagSemProc.07212.3
Abstract
We discuss the impact of data structures in quantifier elimination.
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 $mathbb{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 $Omega(4^{n})$.
Subject Classification
Keywords
- Quantifier elimination
- dense representation
- instrinsic
- lower bound
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads