From 145e7850d1954a910f8ffa07c39b72af43b55508 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 13 Sep 2008 17:59:37 +0200 Subject: [PATCH] Removed ranking from the Epilogue. --- epilog.tex | 10 ---------- 1 file changed, 10 deletions(-) diff --git a/epilog.tex b/epilog.tex index d4dfd18..d655ddf 100644 --- a/epilog.tex +++ b/epilog.tex @@ -33,16 +33,6 @@ from the upper ones. The known algorithms run on the Pointer machine and we do not know if using a~stronger model can help. -For the ranking problems, the situation is completely different. We have shown -linear-time algorithms for three important problems of this kind. The techniques, -which we have used, seem to be applicable to other ranking problems. On the other -hand, ranking of general restricted permutations has turned out to balance on the -verge of $\#{\rm P}$-completeness. All our algorithms run -on the RAM model, which seems to be the only sensible choice for problems of -inherently arithmetic nature. While the unit-cost assumption on arithmetic operations -is not universally accepted, our results imply that the complexity of our algorithm -is dominated by the necessary arithmetics. - Aside from the concrete problems we have solved, we have also built several algorithmic techniques of general interest: the unification procedures using pointer-based bucket sorting (Section \ref{bucketsort}) and the vector computations on the RAM -- 2.39.2