DROPS

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}
}

Search Results

Documents authored by Grimson, Rafael

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

Abstract

Cite as

Thanks for your feedback!

Could not send message