From 8bbc90b8681cf90aa670a94c465e419c733c8815 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 4 Jun 2008 14:54:33 +0200 Subject: [PATCH] Abstract: Final fixes. --- abstract.tex | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/abstract.tex b/abstract.tex index ce4baa0..27a0870 100644 --- a/abstract.tex +++ b/abstract.tex @@ -31,7 +31,7 @@ with the intricate details of various models of computation and even of arithmet itself. We have tried to cover all known important results on both problems and unite them -in a~single coherent theory. At many places, we have attempted to contribute my own +in a~single coherent theory. At many places, we have attempted to contribute our own little stones to this mosaic: several new results, simplifications of existing ones, and last, but not least filling in important details where the original authors have missed some. @@ -615,7 +615,7 @@ the expense of \df{corrupting} a~fraction of the inserted elements by raising their values (the values are however never lowered). This allows for a~trade-off between accuracy and speed, controlled by a~parameter~$\varepsilon$. -\>In the thesis, we describe the exact mechanics of the soft heaps and analyse its complexity. +In the thesis, we describe the exact mechanics of the soft heaps and analyse its complexity. The important properties are characterized by the following theorem: \thmn{Performance of soft heaps, Chazelle \cite{chazelle:softheap}}\id{softheap}% @@ -726,7 +726,7 @@ complexity is therefore an~obvious lower bound on the time complexity of the problem in all other comparison-based models. The downside is that we do not know any explicit construction of the optimal -decision trees, or at least a~non-constructive proof of their complexity. +decision trees, nor even a~non-constructive proof of their complexity. On the other hand, the complexity of any existing comparison-based algorithm can be used as an~upper bound on the decision tree complexity. Also, we can construct an~optimal decision tree using brute force: @@ -1356,7 +1356,7 @@ We have seen the many facets of the minimum spanning tree problem. It has turned out that while the major question of the existence of a~linear-time MST algorithm is still open, backing off a~little bit in an~almost arbitrary direction leads to a~linear solution. This includes classes of graphs with edge -density at least $\lambda_k(n)$ for an~arbitrary fixed~$k$, +density at least $\lambda_k(n)$ (the $k$-th row inverse of the Ackermann's function) for an~arbitrary fixed~$k$, minor-closed classes, and graphs whose edge weights are integers. Using randomness also helps, as does having the edges pre-sorted. -- 2.39.2