A lower bound for the complexity of linear optimization from a quantifier-elimination point of view

Author Rafael Grimson



PDF
Thumbnail PDF

File

DagSemProc.07212.3.pdf
  • Filesize: 168 kB
  • 6 pages

Document Identifiers

Author Details

Rafael Grimson

Cite AsGet 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})$.
Keywords
  • Quantifier elimination
  • dense representation
  • instrinsic
  • lower bound

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail