Search Results

Documents authored by Grimson, Rafael


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

Authors: Rafael Grimson

Published in: Dagstuhl Seminar Proceedings, Volume 7212, Constraint Databases, Geometric Elimination and Geographic Information Systems (2007)


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})$.

Cite as

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)


Copy BibTex To Clipboard

@InProceedings{grimson:DagSemProc.07212.3,
  author =	{Grimson, Rafael},
  title =	{{A lower bound for the complexity of linear optimization from a quantifier-elimination point of view}},
  booktitle =	{Constraint Databases, Geometric Elimination and Geographic Information Systems},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7212},
  editor =	{Bernd Bank and Max J. Egenhofer and Bart Kuijpers},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07212.3},
  URN =		{urn:nbn:de:0030-drops-12837},
  doi =		{10.4230/DagSemProc.07212.3},
  annote =	{Keywords: Quantifier elimination, dense representation, instrinsic, lower bound}
}
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