X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=rank.tex;h=b4b8ffebd0de6ccb00c282875c08264b17892855;hb=HEAD;hp=91121ab9a9806bcf305313d42bd9bf404d5220d1;hpb=ff0a4590f542ae6559682741b5dbaeb09e6d4223;p=saga.git

diff --git a/rank.tex b/rank.tex
index 91121ab..b4b8ffe 100644
--- a/rank.tex
+++ b/rank.tex
@@ -430,7 +430,8 @@ determine whether there exists at least one permutation satisfying a~given set o
 
 \thm
 There is an~algorithm which decides in time $\O(n^{1/2}\cdot m)$ whether there exists
-a~permutation satisfying a~given restriction graph.
+a~permutation satisfying a~given restriction graph. The $n$ and~$m$ are the number
+of vertices and edges of the restriction graph.
 
 \proof
 It is sufficient to verify that there exists a~perfect matching in the
@@ -442,19 +443,19 @@ and Schrijver \cite{schrijver} for more references on flows and matchings.)
 \qed
 
 \para
-The bad news is that computing the permanent is known to be~$\#P$-complete even
+The bad news is that computing the permanent is known to be~$\#\rm P$-complete even
 for zero-one matrices (as proven by Valiant \cite{valiant:permanent}).
 As a~ranking function for a~set of~matchings can be used to count all such
 matchings, we obtain the following theorem:
 
 \thm\id{pcomplete}%
 If there is a~polynomial-time algorithm for lexicographic ranking of permutations with
-a~set of restrictions which is a~part of the input, then $P=\#P$.
+a~set of restrictions which is a~part of the input, then $\rm P=\#P$.
 
 \proof
 We will show that a~polynomial-time ranking algorithm would imply a~po\-ly\-nom\-ial-time
 algorithm for computing the permanent of an~arbitrary zero-one matrix, which
-is a~$\#P$-complete problem.
+is a~$\#\rm P$-complete problem.
 
 We know from Lemma \ref{permchar} that non-zero
 summands in the permanent of a~zero-one matrix~$M$ correspond to permutations restricted
@@ -463,6 +464,7 @@ therefore equal to the number of such permutations, which is one more than the
 rank of the lexicographically maximum such permutation.
 It therefore remains to show that we can find the lexicographically maximum
 permutation permitted by~$G$ in polynomial time.
+\looseness=1 %%HACK%%
 
 We can determine $\pi[1]$ by trying all the possible values permitted by~$G$
 in decreasing order and stopping as soon as we find~$\pi[1]$ which can be
@@ -481,6 +483,7 @@ the counting problem is easy (and it is also easy for subgraphs obtained
 by deleting vertices), ranking is easy as well. The key will be once again
 a~recursive structure, similar to the one we have seen in the case of plain
 permutations in \ref{permrec}.
+\looseness=1 %%HACK%%
 
 \nota\id{restnota}%
 As we will work with permutations on different sets simultaneously, we have
@@ -508,6 +511,7 @@ $M[1,a]=1$ for $a=R_A(\pi[1])$ and $\pi'$ satisfies a~restriction matrix~$M'=M^{
 This translates to the following counterparts of algorithms \ref{rankalg}
 and \ref{unrankalg}:
 
+\goodbreak  %%HACK%%
 \alg\id{rrankalg}%
 $\<Rank>(\pi,i,n,A,M)$: Compute the lexicographic rank of a~permutation $\pi[i\ldots n]\in{\cal P}_{A,M}$.
 
@@ -566,13 +570,17 @@ spend time $\O(n^2)$ on operations with the set~$A$, $\O(n^4)$ on matrix manipul
 and $\O(n^2\cdot t(n))$ by the computations of the~$N_0$'s.
 \qed
 
-\rem
-In cases where the efficient evaluation of the permanent is out of our reach,
+\paran{Approximation}%
+In cases where efficient evaluation of the permanent is out of our reach,
 we can consider using the fully-polynomial randomized approximation scheme
 for the permanent described by Jerrum, Sinclair and Vigoda \cite{jerrum:permanent}.
-Then we get an~approximation scheme for the ranks.
+They have described a~randomized algorithm that for every $\varepsilon>0$
+approximates the value of the permanent of an~$n\times n$ matrix with non-negative
+entries. The output is within relative error~$\varepsilon$ from the correct value with
+probability at least~$1/2$ and the algorithm runs in time polynomial in~$n$ and~$1/\varepsilon$.
+From this, we can get a~similar approximation scheme for the ranks.
 
-\rem
+\paran{Special restriction graphs}%
 There are also deterministic algorithms for computing the number of perfect matchings
 in various special graph families (which imply polynomial-time ranking algorithms for
 the corresponding families of permutations). If the graph is planar, we can
@@ -580,7 +588,7 @@ use the Kasteleyn's algorithm \cite{kasteleyn:crystals} based on Pfaffian
 orientations which runs in time $\O(n^3)$.
 It has been recently extended to arbitrary surfaces by Yuster and Zwick
 \cite{yuster:matching} and sped up to $\O(n^{2.19})$. The counting problem
-for arbitrary minor-closed classes (cf.~section \ref{minorclosed}) is still
+for arbitrary minor-closed classes (cf.~Section \ref{minorclosed}) is still
 open.
 
 %--------------------------------------------------------------------------------