From c6687beaef7cf71aeba58ed20d4fd5b2e4842290 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 25 Feb 2008 15:18:39 +0100 Subject: [PATCH] Minor changes. --- PLAN | 1 + rank.tex | 11 ++++++++--- 2 files changed, 9 insertions(+), 3 deletions(-) diff --git a/PLAN b/PLAN index b57a77e..b4699d6 100644 --- a/PLAN +++ b/PLAN @@ -66,6 +66,7 @@ Ranking: - the general perspective: is it only a technical trick? - move description of the ranking set to the chapter on models? - ranking of permutations on general sets, relationship with integer sorting +- mention approximation of permanent Notation: diff --git a/rank.tex b/rank.tex index 73c3479..2606aba 100644 --- a/rank.tex +++ b/rank.tex @@ -426,11 +426,16 @@ in decreasing order and stopping as soon as we find~$\pi[1]$ which can be extended to a~complete permutation. We can do this for example by using the Dinic's algorithm as described above on~the graph of remaining restrictions (i.e., $G$ with the vertices 1 and~$\pi[1]$ and removed together with the corresponding -edges). Once we have~$\pi[1]$, we can fix it and proceed with finding $\pi[2]$ -using the reduced graph. This way we construct the whole maximal permutation~$\pi$ -in~$\O(n^2)$ calls to the Dinic's algorithm. +edges). Once we have~$\pi[1]$, we can fix it and proceed by finding $\pi[2]$ +in the same way, using the reduced graph. This way we construct the whole +maximal permutation~$\pi$ in~$\O(n^2)$ calls to the Dinic's algorithm. \qed +\para +However, the hardness of computing the permanent is the worst obstacle. +We will show that whenever we are given a~set of restrictions for which +the counting problem is easy (and it is also easy for subgraphs obtained +by deleting vertices), ranking is easy as well. \endpart -- 2.39.5