TAOCP 7.2.2.1 Exercise 31
The active item list in Algorithm X is maintained as a circular doubly linked list via $\text{LLINK}$ and $\text{RLINK}$ pointers on item headers.
Section 7.2.2.1: Dancing Links
Exercise 31. [M21] The running time of Algorithm X depends on the order of primary items in the active list, as well as on the order of options in the individual item lists. Explain how to randomize the algorithm so that (a) every item list is in random order after step X1; (b) step X3 chooses randomly among items with the minimum LB.
Verified: yes
Solve time: 1m05s
Solution
The active item list in Algorithm X is maintained as a circular doubly linked list via $\text{LLINK}$ and $\text{RLINK}$ pointers on item headers. Each item header $i$ also stores the current lower bound value $\text{LEN}(i)$, equal to the number of active options containing $i$. Randomization can be introduced without changing correctness by making both the initial ordering of this list and the tie-breaking rule in step X3 stochastic.
To randomize the item order after step X1, the construction phase of the data structure is modified so that the doubly linked list of item headers is not assembled in a fixed deterministic sequence. Instead, the set of items is first given an arbitrary total order produced by a uniform random permutation of ${1,2,\ldots,N}$. The $\text{RLINK}$ and $\text{LLINK}$ pointers are then initialized according to this permutation so that the active list follows the randomized order cyclically. Since Algorithm X only traverses this structure via pointer operations, this change affects only the order in which items are encountered, not the set of states reached.
Randomization of individual option lists is performed in the same way. For each item $i$, the vertical list of nodes representing options containing $i$ is a doubly linked circular list. After all nodes are created, the nodes in each such list are permuted uniformly at random and then reconnected via their $\text{DLINK}$ and $\text{ULINK}$ fields in the permuted order. Because Algorithm X processes each list by following these pointers, this ensures that the order in which options are examined within step X3 is also randomized without changing the underlying combinatorial structure.
For step X3, let $S$ be the set of active items $i$ that minimize $\text{LEN}(i)$ among all currently active items. The modification is to select an element of $S$ uniformly at random. This can be implemented by a single scan of the active list: initialize a counter $k \leftarrow 0$ and a chosen item variable $i^\star \leftarrow 0$. As each item $i$ is encountered during traversal of the active list, compare $\text{LEN}(i)$ with the current minimum value $\mu$. If $\text{LEN}(i) < \mu$, reset $\mu \leftarrow \text{LEN}(i)$, set $k \leftarrow 1$, and set $i^\star \leftarrow i$. If $\text{LEN}(i) = \mu$, increment $k \leftarrow k+1$ and replace $i^\star$ by $i$ with probability $1/k$, leaving it unchanged otherwise. After the scan completes, $i^\star$ is uniformly distributed over all items attaining the minimum $\text{LEN}$ value, so step X3 proceeds with $i \leftarrow i^\star$.
This modification preserves the deterministic state transitions of cover and uncover, since those procedures are unchanged, while replacing deterministic choice points by uniform random selections over the prescribed candidate sets.
This completes the solution. ∎