From 9297cb765d9ed0affcf98bfdb47c7c4f25d7211e Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Wed, 27 Feb 2008 21:37:09 +0100
Subject: [PATCH] More references. More!

---
 PLAN       |  1 -
 adv.tex    |  5 +++--
 biblio.bib | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
 rank.tex   | 17 +++++++++++++++++
 4 files changed, 69 insertions(+), 3 deletions(-)

diff --git a/PLAN b/PLAN
index 432e52d..3e7490d 100644
--- a/PLAN
+++ b/PLAN
@@ -67,7 +67,6 @@ Ranking:
 
 - the general perspective: is it only a technical trick?
 - ranking of permutations on general sets, relationship with integer sorting
-- mention approximation of permanent
 
 Notation:
 
diff --git a/adv.tex b/adv.tex
index 8c02792..2941a98 100644
--- a/adv.tex
+++ b/adv.tex
@@ -32,8 +32,9 @@ Non-trivial minor-closed classes include:
 
 \para
 Many of the nice structural properties of planar graphs extend to
-minor-closed classes, too (see \cite{diestel:gt} for a~nice overview
-of this theory). The most important property is probably the characterization
+minor-closed classes, too (see \cite{lovasz:minors} for a~nice survey
+of this theory and \cite{diestel:gt} for some of the deeper results).
+The most important property is probably the characterization
 of such classes in terms of their forbidden minors.
 
 \defn
diff --git a/biblio.bib b/biblio.bib
index fccd482..d8ba965 100644
--- a/biblio.bib
+++ b/biblio.bib
@@ -821,3 +821,52 @@ inproceedings{ pettie:minirand,
   pages={189--201},
   year={1979}
 }
+
+@article{ jerrum:permanent,
+  title={{A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries}},
+  author={Jerrum, M. and Sinclair, A. and Vigoda, E.},
+  journal={Journal of the ACM},
+  volume={51},
+  number={4},
+  pages={671--697},
+  year={2004}
+}
+
+@article{ kasteleyn:crystals,
+  title={{Graph theory and crystal physics}},
+  author={Kasteleyn, P. W.},
+  journal={Graph Theory and Theoretical Physics},
+  publisher={Academic Press, London},
+  pages={43--110},
+  year={1967}
+}
+
+@article{ yuster:matching,
+  title={{Maximum matching in graphs with an excluded minor}},
+  author={Yuster, R. and Zwick, U.},
+  journal={Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms},
+  pages={108--117},
+  year={2007},
+  publisher={Society for Industrial and Applied Mathematics Philadelphia, PA, USA}
+}
+
+@article{ mucha:matching,
+  title={{Maximum Matchings in Planar Graphs via Gaussian Elimination}},
+  author={Mucha, M. and Sankowski, P.},
+  journal={Algorithmica},
+  volume={45},
+  number={1},
+  pages={3--20},
+  year={2006},
+  publisher={Springer}
+}
+
+@article {lovasz:minors,
+  title={{Graph Minor Theory}},
+  author={Lov\'asz, L.},
+  journal={Bulletin of the American Mathematical Society},
+  volume={43},
+  number={1},
+  pages={75--86},
+  year={2005}
+}
diff --git a/rank.tex b/rank.tex
index 5be516d..c457a81 100644
--- a/rank.tex
+++ b/rank.tex
@@ -561,6 +561,23 @@ 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,
+we can consider using the fully-polynomial randomized approximation scheme
+for the permanent described by Jerrum, Sinclair and Vigoda in \cite{jerrum:permanent}.
+We then get an~approximation scheme for the ranks.
+
+\rem
+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
+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
+open.
+
 %--------------------------------------------------------------------------------
 
 \section{Hatcheck lady and other derangements}
-- 
2.39.2