de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Generalized and improved constructive separation bound for real algebraic expressions

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45391

Schirra,  Stefan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

2000-1-004
(beliebiger Volltext), 10KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Mehlhorn, K., & Schirra, S.(2000). Generalized and improved constructive separation bound for real algebraic expressions (MPI-I-2000-1-004). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-6D56-E
Zusammenfassung
We prove a separation bound for a large class of algebraic expressions specified by expression dags. The bound applies to expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, $k$-th root operations for integral $k$, and taking roots of polynomials whose coefficients are given by the values of subexpressions. The (logarithm of the) new bound depends linearly on the algebraic degree of the expression. Previous bounds applied to a smaller class of expressions and did not guarantee linear dependency. \ignore{In~\cite{BFMS} the dependency was quadratic. and in the Li-Yap bound~\cite{LY} the dependency is usually linear, but may be even worse than quadratic.}