X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=sidebyside;f=opt.tex;h=9ead62d62fea2e87293f3b3c70c7c231182ba987;hb=5a37003ab17662e8074864c7f4b4b5bddb1c6e6c;hp=86402c617a708fe47db3e157138d6623f74e16af;hpb=36012b9518adaee9da67e653cbc01f541a1273bf;p=saga.git diff --git a/opt.tex b/opt.tex index 86402c6..9ead62d 100644 --- a/opt.tex +++ b/opt.tex @@ -4,15 +4,15 @@ \chapter{Approaching Optimality}\id{optchap}% -\section{Soft heaps} +\section{Soft heaps}\id{shsect}% A~vast majority of MST algorithms that we have encountered so far is based on the Tarjan's Blue rule (Lemma \ref{bluelemma}). The rule serves to identify edges that belong to the MST, while all other edges are left in the process. This unfortunately means that the later stages of computation spend most of -their time on these useless edges. A~notable exception is the randomized +their time on these edges that never enter the MSF. A~notable exception is the randomized algorithm of Karger, Klein and Tarjan. It adds an~important ingredient: it uses -Red rule (Lemma \ref{redlemma}) to filter out edges that are guaranteed to stay +the Red rule (Lemma \ref{redlemma}) to filter out edges that are guaranteed to stay outside the MST, so that the graphs with which the algorithm works get smaller with time. @@ -29,38 +29,50 @@ similar to the Vuillemin's binomial heaps \cite{vuillemin:binheap} or Fredman's and Tarjan's Fibonacci heaps \cite{ft:fibonacci}. The soft heaps run faster at the expense of \df{corrupting} a~fraction of the inserted elements by raising their values (the values are however never lowered). This allows for -an~trade-off between accuracy and speed controlled by a~parameter~$\varepsilon$. +a~trade-off between accuracy and speed, controlled by a~parameter~$\varepsilon$. The heap operations take $\O(\log(1/\varepsilon))$ amortized time and at every moment at most~$\varepsilon n$ elements of the~$n$ elements inserted can be corrupted. -\defnn{Soft heap operations}% -The soft heap contains a~set of distinct items from a~totally ordered universe and it +\defnn{Soft heap interface}% +The \df{soft heap} contains a~set of distinct items from a~totally ordered universe and it supports the following operations: \itemize\ibull \:$\(\varepsilon)$ --- Create an~empty soft heap with the given accuracy parameter~$\varepsilon$. -\:$\(H,x)$ --- Insert a~new item~$x$ to the heap~$H$. +\:$\(H,x)$ --- Insert a~new item~$x$ into the heap~$H$. \:$\(P,Q)$ --- Merge two heaps into one, more precisely move all items of a~heap~$Q$ - to the heap~$P$, destroying~$Q$ in the process (both heaps must have the same~$\varepsilon$). + to the heap~$P$, destroying~$Q$ in the process. Both heaps must have the same~$\varepsilon$. \:$\(H)$ --- Delete the minimum item of the heap~$H$ and return its value (optionally signalling that the value has been corrupted). \:$\(H)$ --- Destroy the heap and return a~list of all items contained in it (again optionally marking those corrupted). \endlist +\>For every item, we will distinguish between its \df{original} value at the time +of insertion and its \df{current} value in the heap, which is possibly corrupted. + \examplen{Linear-time selection} We can use soft heaps to select the median (or generally the $k$-th smallest element) of a~sequence. We insert all $n$~elements to a~soft heap with error rate $\varepsilon=1/3$. -Then we delete the minimum about $n/3$ times and we remember the current (possibly corrupted) -value~$x$ of the last element deleted. This~$x$ is greater or equal than the current -values of the previously deleted elements and thus also than their correct values. +Then we delete the minimum about $n/3$ times and we remember the current value~$x$ +of the last element deleted. This~$x$ is greater or equal than the current +values of the previously deleted elements and thus also than their original values. On the other hand, the current values of the $2n/3$ elements remaining in the heap are greater than~$x$ and at most $n/3$ of them are corrupted. Therefore at least $n/3$ -elements are greater than~$x$ and at least $n/3$ ones are smaller. Depending on the value -of~$k$, we can always throw away one of these parts and recurse on the rest (similarly to -the Hoare's Quickselect algorithm \cite{hoare:qselect}). The total time complexity will -be $\O(n+(2/3)\cdot n+(2/3)^2\cdot n+\ldots) = \O(n)$. We have obtained a~nice alternative to the standard -linear-time selection algorithm by Blum \cite{blum:selection}. The same trick can be used +original elements are greater than~$x$ and at least $n/3$ ones are smaller. + +This allows us to use the~$x$ as a~pivot in the traditional divide-and-conquer algorithm +for selection (cf.~Hoare's Quickselect algorithm \cite{hoare:qselect}): We split the +input elements to three parts: $A$~contains those less than~$x$, $B$~those equal to~$x$ +and $C$~those greater than~$x$. If $k\le\vert A\vert$, the desired element lies in~$A$, +so we can continue by finding the $k$-th smallest element of~$A$. If $\vert A\vert < k \le \vert +A\vert + \vert B\vert$, the desired element is $x$~itself. Otherwise, we search for the +$(k-\vert A\vert-\vert B\vert)$-th smallest element of~$C$. Either way, we have removed +at least $n/3$ items, so the total time complexity is +$\O(n+(2/3)\cdot n+(2/3)^2\cdot n+\ldots) = \O(n)$. + +We have obtained a~nice alternative to the standard +linear-time selection algorithm of Blum \cite{blum:selection}. The same trick can be used to select a~good pivot in Quicksort \cite{hoare:qsort}, leading to time complexity $\O(n\log n)$ in the worst case. @@ -79,8 +91,8 @@ permanently occupied. The left sons will be called \df{white}, the right ones The first value in every list is called the \df{controlling key} of the vertex, denoted by $\(v)$. If the list is empty, we keep the most recently used -value or we set $\(v)=+\infty$. The \ obey the standard \df{heap order} ---- a~\ of a~parent is always smaller than the \'s of its sons. +value or we set $\(v)=+\infty$. The \s obey the standard \df{heap order} +--- a~\ of a~parent is always smaller than the \s of its sons. Each vertex is also assigned its \df{rank,} which is a~non-negative integer. The ranks of leaves are always zero, the rank of every internal vertex can be @@ -104,7 +116,7 @@ ranks, colors and the ancestor relation. The queues have a~nice recursive structure. We can construct a~queue of rank~$k$ by \df{joining} two queues of rank~$k-1$ under a~new root. The root will inherit the item list of one of the original roots and also its \. To preserve the heap order, we will choose -the one whose \ is smaller. +the son whose \ is smaller. Sometimes, we will also need to split a~queue to smaller queues. We will call this operation \df{dismantling} the queue and it will happen only in cases when the item list in the root @@ -137,8 +149,8 @@ its leftmost path contains at least~$k/2$ vertices. the heap of the smaller rank and we insert its queues to the other heap. If two queues of the same rank~$k$ appear in both lists, we \em{join} them to a~single queue of rank~$k+1$ as already described and we propagate the new queue as -a~\df{carry} to the next iteration, similarly to addition of binary numbers. -Finally we have to update the suffix minima by walking the new list backwards +a~\df{carry} to the next iteration. (This is similar to addition of binary numbers.) +Finally, we have to update the suffix minima by walking the new list backwards from the last inserted item. \em{Creation} of a~new soft heap is trivial, \em{insertion} is handled by creating @@ -156,7 +168,7 @@ a~single-element heap and melding it to the destination heap. \algn{Melding of two soft heaps} \algo \algin Two soft heaps~$P$ and~$Q$. -\:If $\(P) < \(Q)$, exchange the item lists of~$P$ and~$Q$. +\:If $\(P) < \(Q)$, exchange the queue lists of~$P$ and~$Q$. \:$p\=\(P)$. \brk\cmt{Whenever we run into an~end of a~list in this procedure, we assume that there is an~empty queue of infinite rank there.} @@ -189,7 +201,7 @@ there is an~empty queue of infinite rank there.} \algout An~updated heap~$H$. \endalgo -\para +\paran{Corruption}% So far, the mechanics of the soft heaps were almost identical to the binomial heaps and the reader could rightfully yawn. The things are going to get interesting now as we approach the parts where corruption of items takes place. @@ -213,7 +225,7 @@ the higher is the rank, the longer list will be allowed. \. There we look inside the item list of the root of the queue. We remove the \em{last} item from the list (we do not want the \ to change) and we return it as the minimum. (It is not necessarily the real minimum of all items, but always the minimum of their -possibly corrupted values.) +current, possibly corrupted values.) If the list becomes empty, we \em{refill} it with items from the lower levels of the same queue. This process can be best described recursively: We ask the left son to refill itself @@ -224,19 +236,19 @@ new left son to the parent. This way we obey the heap order and at the same time the white left son free of items. Occasionally, we repeat this process once again and we concatenate the resulting lists -(we append the latter list to the former, using the smaller of the two \'s). This +(we append the latter list to the former, using the smaller of the two \s). This makes the lists grow longer and we want to do that roughly on every other level of the tree. The exact condition will be that either the rank of the current vertex is odd, or the difference in ranks between this vertex and its right son is at least two. If refilling of the left son fails because there are no more items in that subtree -(we report this by setting its \ to $+\infty$), the current vertex is no longer +(we report this by setting the \ to $+\infty$), the current vertex is no longer needed --- the items would just pass through it unmodified. We therefore want to remove it. Instead of deleting it directly, we rather make it point to its former grandsons and we remove the (now orphaned) original son. This helps us to ensure that both sons always keep the same rank, which will be useful for the analysis. -When all refilling is done, we update the suffix minima by walking from the current +When the refilling is over, we update the suffix minima by walking from the current queue to the head of the heap exactly as we did in the \ procedure. Our only remaining worry is that the Rank invariant can be broken after the @@ -254,7 +266,7 @@ Let us translate these ideas to real (pseudo)code: \algin A~soft heap~$H$. \:Use \ of the head queue of~$H$ to locate the queue~$q$ with the smallest \. \:Remove the final element~$x$ of the item list in the root of~$q$. -\:If the item list is empty: +\:If the item list became empty: \::Count the vertices on the leftmost path of~$q$. \::If there are less than $\(q)$ of them: \:::Remove~$q$ from the list of queues. @@ -308,7 +320,7 @@ $$\ell(v) \le \max(1, 2^{\lceil \(v)/2 \rceil - r/2}).$$ \proof Initially, all item lists contain at most one item, so the inequality trivially -holds. Let us continue by induction. Melds can affect it only in the favorable +holds. Let us continue by induction. Melds can affect the inequality only in the favorable direction (they occasionally move an~item list to a~vertex of a~higher rank) and so do deletes (they only remove items from lists). The only potentially dangerous place is the \ procedure. @@ -319,7 +331,7 @@ no joining takes place and~$\ell(v)$ is still~1. Otherwise we join when either $\(v)$ is odd or $\(w) < \(v)-1$ for any son~$w$ of~$v$ (remember that both sons have the same rank). In both cases, $\lceil\(w)/2\rceil \le \lceil\(v)/2\rceil - 1$. By the induction hypothesis, the size of each -of the two joined lists is at most $2^{\max(1,\lceil\(v)/2\rceil - 1 - r/2)}$, +of the two lists being joined is at most $2^{\max(1,\lceil\(v)/2\rceil - 1 - r/2)}$, so the new list has at most $2^{\lceil\(v)/2\rceil - r/2}$ items. (The maximum has disappeared since $\(v)>r$ and therefore the desired bound is at least~2.) \qed @@ -391,11 +403,11 @@ and each internal vertex represents a~heap arisen from melding its sons. The lef son will be the one with the greater or equal rank. We therefore want to bound the sum of ranks of all right sons. -For every right son, we will distribute the change for its rank~$k$ among all leaves +For every right son, we will distribute the charge for its rank~$k$ among all leaves in its subtree. There are at least $2^k$ such leaves. No leaf ever receives the same rank twice, because the ranks of right sons on every path from the root of the tree to a~leaf are strictly decreasing. (This holds because melding of two heaps -always produces a~heap of a~strictly greater rank.) Hence at most~$n/2^k$ +always produces a~heap of a~rank strictly greater than the smaller of the input ranks.) Hence at most~$n/2^k$ right sons have rank~$k$ and the total time charged against the leaves is bounded by: $$ \sum_{k=0}^{\rm max. rank}k\cdot {n\over 2^k} \le n\cdot\sum_{k=0}^\infty {k\over 2^k} = 2n. @@ -496,7 +508,7 @@ implemented on the Pointer Machine in constant amortized time. We will recycle the idea of ``yardsticks'' from Section \ref{bucketsort}. We create a~yardstick --- a~doubly linked list whose elements represent the possible values of a~rank. Every vertex of a~queue will store its rank as a~pointer to -the corresponding ``tick'' of the yardstick. We will extend the list as necessary. +the corresponding ``tick'' of the yardstick. We will extend the list whenever necessary. Comparison of two ranks for equality is then trivial, as is incrementing or decrementing the rank by~1. Testing whether a~rank is odd can be handled by storing an~odd/even @@ -507,7 +519,7 @@ in time proportional to the smaller of them, which is the real cost of the meld The comparisons in steps 5 and~6 are trickier, but since the ranks of the elements put to~$P$ are strictly increasing, we can start walking the list at the rank of the previous element in~$P$. The cost is then the difference between the current and the previous rank -and their sum telescopes, again to the real cost of the meld. +and the sum of these differences telescopes, again to the real cost of the meld. \qed Now we can put the bits together and laurel our effort with the following theorem: @@ -553,7 +565,7 @@ these trees are contained in the MST, so by the Contraction lemma (\ref{contlemma}) we can contract each of them to a~single vertex and iterate the algorithm on the resulting graph. -We can try implanting the soft heap in this algorithm, preferably in its earlier +We can try implanting the soft heap in this algorithm, preferably in the earlier version without active edges (\ref{jarnik}) as the soft heap lacks the \ operation. This brave, but somewhat simple-minded attempt is however doomed to fail. The reason is of course the corruption of items inside the heap, which @@ -577,8 +589,9 @@ of the edges $e,f$ such that all edges on this path are lighter than either $e$ \example\id{jarniscont}% Let us see that when we stop the Jarn\'\i{}k's algorithm at some moment and we take a~subgraph~$C$ induced by the constructed tree, this subgraph is contractible. -Indeed, when we consider any two distinct edges $uv, xy$ ($u,x\in C$ and $v,y\not\in C$), -they enter the algorithm's heap at some time. Without loss of generality $uv$~is the first. +Indeed, when we consider any two distinct edges $uv, xy$ having exactly one endpoint in~$C$ +(w.l.o.g.~$u,x\in C$ and $v,y\not\in C$), +they enter the algorithm's heap at some time. Without loss of generality $uv$~enters it earlier. Before the algorithm reaches the vertex~$x$, it adds the whole path $ux$ to the tree. As the edge~$uv$ never leaves the heap, all edges on the path $ux$ must be lighter than this edge. @@ -622,7 +635,7 @@ When~$G$ is a~weighted graph and~$R$ a~subset of its edges, we will use $G\crpt R$ to denote an arbitrary graph obtained from~$G$ by increasing the weights of some of the edges in~$R$. As usually, we will assume that all edges of this graph have pairwise distinct weights. While this is technically not true for the corruption -caused by soft heaps, we can easily make the weights unique. +caused by soft heaps, we can easily make it so. Whenever~$C$ is a~subgraph of~$G$, we will use $R^C$ to refer to the edges of~$R$ with exactly one endpoint in~$C$ (i.e., $R^C = R\cap \delta(C)$). @@ -633,7 +646,7 @@ for some set~$R$ of edges. Then $\msf(G) \subseteq \msf(C) \cup \msf((G/C) \setm \proof We will modify the proof of the previous lemma. We will again consider all possible types -of edges which do not belong to the right-hand side and we will show that they are the +of edges that do not belong to the right-hand side and we will show that they are the heaviest edges of certain cycles. Every edge~$g$ of~$G$ lies either in~$C$, or in $H=(G/C)\setminus R^C$, or possibly in~$R^C$. @@ -652,7 +665,7 @@ trick with expanding the vertex~$c$ to~$P$ in the cycle~$C$. Hence $g\not\in\mst \para We still intend to mimic the Iterative Jarn\'\i{}k's algorithm. We will partition the given graph to a~collection~$\C$ of non-overlapping contractible subgraphs called \df{clusters} and we put aside all edges that got corrupted in the process. -We recursively compute the MSF of that subgraphs and of the contracted graph. Then we take the +We recursively compute the MSF of those subgraphs and of the contracted graph. Then we take the union of these MSF's and add the corrupted edges. According to the previous lemma, this does not produce the MSF of~$G$, but a~sparser graph containing it, on which we can continue. @@ -714,7 +727,7 @@ Claim~3: The trees have at most~$t$ vertices each, which limits the size of the $C_i$'s as well. Claim~4: We can show that each connected component has $t$~or more vertices as we already did -in the proof of Lemma \ref{ijsize}: How can a~new tree stop growing? Either it gathers +in the proof of Lemma \ref{ijsize}: How can a~new tree stop growing? Either it acquires $t$~vertices, or it joins one of the existing trees (this only increases the size of the component), or the heap becomes empty (which means that the tree spans a~full component of the current graph and hence also of the final~$G\setminus R^\C$). @@ -769,7 +782,7 @@ and additionally $\O(n)$ on identifying the live vertices. %-------------------------------------------------------------------------------- -\section{Decision trees} +\section{Decision trees}\id{dtsect}% The Pettie's and Ramachandran's algorithm combines the idea of robust partitioning with optimal decision trees constructed by brute force for very small subgraphs. In this section, we will @@ -788,14 +801,14 @@ Formally, the decision trees are defined as follows: \defnn{Decision trees and their complexity}\id{decdef}% A~\df{MSF decision tree} for a~graph~$G$ is a~binary tree. Its internal vertices -are labeled with pairs of $G$'s edges to be compared, each of the two outgoing edges +are labeled with pairs of $G$'s edges to be compared, each of the two outgoing tree edges corresponds to one possible result of the comparison.\foot{There are two possible outcomes since there is no reason to compare an~edge with itself and we, as usually, expect that the edge weights are distinct.} Leaves of the tree are labeled with spanning trees of the graph~$G$. A~\df{computation} of the decision tree on a~specific permutation of edge weights -in~$G$ is a~path from the root to a~leaf such that the outcome of every comparison +in~$G$ is the path from the root to a~leaf such that the outcome of every comparison agrees with the edge weights. The result of the computation is the spanning tree assigned to its final leaf. A~decision tree is \df{correct} iff for every permutation the corresponding @@ -815,32 +828,32 @@ The \df{decision tree complexity} $D(m,n)$ of the MSF problem is the maximum of~ over all graphs~$G$ with $n$~vertices and~$m$ edges. \obs -Decision trees are the most general comparison-based computation model possible. -The only operations which count in the time complexity are the comparisons. All +Decision trees are the most general deterministic comparison-based computation model possible. +The only operations that count in its time complexity are comparisons. All other computation is free, including solving NP-complete problems or having access to an~unlimited source of non-uniform constants. The decision tree complexity is therefore an~obvious lower bound on the time complexity of the -problem in all other models. +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. On the other hand, the complexity of any existing comparison-based algorithm -can be used as an~upper bound for the decision tree complexity. For example: +can be used as an~upper bound on the decision tree complexity. For example: \lemma $D(m,n) \le 4/3 \cdot n^2$. \proof -Let us count the comparisons performed by the Contractive Bor\o{u}vka's algorithm. +Let us count the comparisons performed by the Contractive Bor\o{u}vka's algorithm (\ref{contbor}), tightening up the constants in its previous analysis in Theorem \ref{contborthm}. In the first iteration, each edge participates in two comparisons -(one for each its endpoint), so the algorithm performs at most $2m \le 2{n\choose 2} \le n^2$ +(one per endpoint), so the algorithm performs at most $2m \le 2{n\choose 2} \le n^2$ comparisons. Then the number of vertices drops at least by a~factor of two, so the subsequent iterations spend at most $(n/2)^2, (n/4)^2, \ldots$ comparisons, which sums -to less than $n^2\cdot\sum_{i=0}^\infty (1/4)^i = 4/3 \cdot n^2$. Between the phases, +to less than $n^2\cdot\sum_{i=0}^\infty (1/4)^i = 4/3 \cdot n^2$. Between the Bor\o{u}vka steps, we flatten the multigraph to a~simple graph, which also needs some comparisons, but for every such comparison we remove one of the participating edges, which saves -at least one comparison in the subsequent phases. +at least one comparison in the subsequent steps. \qed \para @@ -967,7 +980,7 @@ the optimal decision tree for~$G$ to another of the same depth, but without inte comparisons. Then we prove by induction on~$k$ and then on the depth of the tree that this tree can be re-arranged, so that every computation first compares edges from~$C_1$, then from~$C_2$ and so on. This means that the tree can be decomposed -to decision trees for the $C_i$'s. Also, without loss of generality all trees for +to decision trees for the $C_i$'s. Also, without loss of efficiency all trees for a~single~$C_i$ can be made isomorphic to~${\cal D}(C_i)$. \qed @@ -1111,12 +1124,14 @@ the time complexity of every comparison-based algorithm. \paran{Complexity of MST}% As we have already noted, the exact decision tree complexity $D(m,n)$ of the MST problem -is still open and so is therefore the time complexity of the optimal algorithm. However, +is still open and so therefore is the time complexity of the optimal algorithm. However, every time we come up with another comparison-based algorithm, we can use its complexity (or more specifically the number of comparisons it performs, which can be even lower) as an~upper bound on the optimal algorithm. -The best explicit comparison-based algorithm known to date achieves complexity $\O(m\timesalpha(m,n))$. +The best explicit comparison-based algorithm known to date achieves complexity $\O(m\timesalpha(m,n))$.\foot{$\alpha(m,n)$ +is a~certain inverse of the Ackermann's function, $\lambda_k(n)$ is the row inverse of the same +function. See \ref{ackerinv} for the exact definitions.} It has been discovered by Chazelle \cite{chazelle:ackermann} as an~improvement of his previous $\O(m\timesalpha(m,n)\cdot\log\alpha(m,n))$ algorithm \cite{chazelle:almostacker}. It is also based on the ideas of this chapter --- in particular the soft heaps and robust contractions. @@ -1127,8 +1142,8 @@ having the optimal algorithm at hand, does not take care about the low-level det bounds the number of comparisons. Using any of these results, we can prove an~Ackermannian upper bound on the optimal algorithm: -\thmn{Upper bound on complexity of the Optimal algorithm} -The time complexity of the Optimal MST algorithm is $\O(m\timesalpha(m,n))$. +\thmn{Upper bound on complexity of the Optimal algorithm}\id{optthm}% +The time complexity of the Optimal MST algorithm is $\O(m\alpha(m,n))$. \proof We bound $D(m,n)$ by the number of comparisons performed by the algorithm of Chazelle \cite{chazelle:ackermann} @@ -1138,8 +1153,8 @@ or Pettie \cite{pettie:ackermann}. Similarly to the Iterated Jarn\'\i{}k's algorithm, this bound is actually linear for classes of graphs that do not have density extremely close to constant: -\cor -The Optimal MST algorithm runs in linear time whenever $m\ge n\cdot a(k,n)$ for any fixed~$k$. +\cor\id{lambdacor}% +The Optimal MST algorithm runs in linear time whenever $m\ge n\cdot \lambda_k(n)$ for any fixed~$k$. \proof Combine the previous theorem with Lemma \ref{alphaconst}.