Generalized Sorting with Predictions

Sorting is arguably the most basic computational task, which is also widely used as an important component of many other algorithms. Pair-wise comparison is the core of most sorting algorithms. In the standard model, it is assumed that we can make comparison between all pairs of elements as we want and they are all of the same cost. However, this may not be the case in many applications. There might be some constrains which forbid us to compare some pairs of elements, or the costs for comparing different pairs of elements may be different. The non-uniform cost sorting model is studied in [3, 4, 6]. A special case called matching nuts and bolts problem is studied in [1, 7].

In this paper, we study the model introduced by Huang, Kannan and Khanna [5], which is known as generalized sorting problem or sorting with forbidden pairs. In this model, only a subset of the comparisons are allowed, and each allowed comparison is of the same cost. We can view the elements as the vertices of a graph, each undirected edge in the graph represents a pair of elements which is allowed to be compared. A comparison of two elements $a,b$ leads to the exposure of the direction of edge $(a,b)$. It is guaranteed that the hidden directed graph is acyclic, and it contains a Hamiltonian path which represents the total order of all elements. Our goal is to adaptively probe edges in $E$ to find out the Hamiltonian path.

For generalized sorting problem, the performance of an algorithm is measured by the number of edges it probes. In standard sorting problem where $G$ is a complete graph, the minimum number of probes required is $\Theta(n\log n)$. For general graphs, one may need more probes. Huang et al. [5] have proved an upper bound of $\widetilde{O}(n^{1.5})$ on the number of probes by giving a randomized algorithm. When the graph is dense and the number of edges is as large as $\binom{n}{2}-q$, [2] proposes a deterministic algorithm which makes $O((n+q)\log n)$ probes together with a randomized algorithm which makes $\widetilde{O}\left(n^{2}/\sqrt{q+n}+n\sqrt{q}\right)$ probes with high probability. Most part of the generalized sorting problem is still open.

Recently, there is an interesting line of research called algorithm design with predictions [9], which is motivated by the observation that by making use of predictions provided by machine learning, one may be able to design a more effective algorithm. Normally, the better the prediction, the better the performance. In this framework, we aim for algorithms which have near optimal performance when the predictions are good, and no worse than the prediction-less case when the predictions have large errors. The above two targets in algorithm design with predictions are called consistency and robustness respectively.

Take the classic binary search algorithm as an example, which can find the position of an existing element in a sorted list in $O(\log n)$ comparisons. It starts by querying the median of the list. However, if a machine learning algorithm can roughly estimate the position of the given element, it may not be always a good idea to start from the middle. Based on this idea, one designed an algorithm with query complexity of $O(\log w)$, where $w$ is the distance between the true position of the element and the estimated one, which measures the accuracy of the prediction. This algorithm can be much better than $O(\log n)$ when $w$ is much smaller than $n$, and no worse than the prediction-less binary search even if the estimation is terribly wrong because $w$ is at most $n$.

Algorithms with predictions are studied for caching [8, 11], ski-rental, online scheduling [10] and other problems. See the nice survey by Mitzenmacher and Vassilvitskii [9].

In this paper, we initiate the study of generalized sorting with predictions. The model is very natural, besides the undirected graph $G=(V,E)$, we are also given an orientation of $G$ as input, which are predictions of the hidden direction of the edges. The number of mis-predicted edges is denoted by $w$. With the help of predictions, we hope to improve the bound of $\tilde{O}(n^{1.5})$ when $w$ is small.

In section 3, we propose a randomized algorithm for the generalized sorting problem and prove that it probes at most $O(n\log n+w)$ edges with high probability. The description of the algorithm is simple while the analysis is quite subtle and involved.

In section 4, we also propose a deterministic algorithm using $O(nw)$ probes, in order to show that when $w$ is as small as a constant, the generalized sorting with prediction problem can be solved using only linear probes.

Note that in the query complexity model, if we have two algorithms $\mathcal{A}$ and $\mathcal{B}$ which use $O(f(n))$ and $O(g(n))$ queries respectively, we can simply merge them into an algorithm $\mathcal{C}$, which simulates $\mathcal{A}$ and $\mathcal{B}$, and make $\mathcal{A}$’s queries and $\mathcal{B}$’s queries alternately. Then $\mathcal{C}$ uses only $O(\min(f(n),g(n)))$ queries. Therefore by combining our algorithms with the one in [5], both consistency and robustness can be achieved.

The algorithm maintains a set of vertices $A$ satisfying $\forall u\in A$, direction of edges between $\mathcal{N}_{in}(\vec{G}_{P},u)$ and $u$ are all known to us (either probed or can be deduced from other probed edges). Notice that the direction of edges in the induced subgraph $G[A]$ must be all known. When $A=V$, the direction of all edges are known and we can easily find the desired Hamiltonian path.

We initialize $A$ as $\emptyset$, then iteratively add ‘ideal vertices’ to $A$, which are defined as follows:

Before adding a vertex $u$ to $A$, we need to determine the direction of edges between $T_{u}$ and $u$ (those between $\mathcal{N}_{in}(\vec{G}_{P},u)\backslash T_{u}$ and $u$ have been already known to be mis-predicted). For an ideal vertex $u$, this can be done by using a straightforward strategy: repeatedly probe the edge $(t,u)$, where $t$ is the largest vertex in $T_{u}$ with respect to $<_{A}$. If the direction of this edge is correct, i.e. $t<_{\vec{E}}u$, we can conclude that the direction of all edges between $T_{u}$ and $u$ are correct by transitivity. We can end this phase and add $u$ to $A$. Otherwise $(t,u)$ is a mis-predicted edge, $t$ is removed from $T_{u}$ and we move on to probe the edge between the new largest vertex in $T_{u}$ and $u$, and so on.

If there is an ideal vertex, we are in an ideal case: by probing only one edge, we either learn the direction of all edges between $T_{u}$ and $u$ and add $u$ into $A$, or find a mis-predicted edge. Notice that each vertex is added to $A$ once, and the wrong probes are charged to the $w$ term of complexity. Therefore we can add all vertices to $A$ in only $O(n+w)$ probes, assuming there is always an ideal vertex in each step.

However, the assumption does not always hold due to the existence of mis-predicted edges, i.e. there may be a time when there is no ideal vertex. We have to relax the conditions to define a new type of vertex to help, which always exists:

An ideal vertex is always active since $S_{u}\subseteq T_{u}$ holds, but there may be some wrong in-neighbors not identified yet (the vertices in $T_{u}\backslash S_{u}$) to prevent an active vertex from being ideal. By cleverly identify the wrong in-neighbors and remove them from $T_{u}$, an active vertex $u$ would become an ideal one and we can use the above strategy again.

As $S_{u}$ is invisible to us, we know neither which vertices are active, nor which in-neighbors of a vertex are wrong, so we turn to focus on the in-neighbors of $u$ which prevent it from being ideal:

1. 1.

   $v\in T_{u}$ s.t. $v\notin A$.

2. 2.

   $v_{1},v_{2}\in T_{u}$ s.t. $(v_{1},v_{2}\in A)\land(v_{1}\not<_{A}v_{2})\land(v_{2}\not<_{A}v_{1})$.

Now consider an active vertex $u$. If such $v$ in case 1 exists, then $(v,u)$ must be a mis-predicted edge. If such $v_{1},v_{2}$ in case 2 exists, there is at least one mis-predicted edge in $(v_{1},u),(v_{2},u)$. By probing $(v,u)$ or both $(v_{1},u),(v_{2},u)$ repeatedly, we can keep removing its wrong in-neighbors from $T_{u}$ and finally make $u$ ideal.

For an inactive vertex $u$, the direction of $(v,u)$ or both of $(v_{1},u),(v_{2},u)$ may be correct, but that tells us $u$ is not active hence is not the vertex we are looking for. In this case the vertex $v$ or the pair of vertices $(v_{1},v_{2})$ is called a certificate for $u$, which proves that $u$ is currently not active.

Once a certificate for $u$ is found, we turn to check the activeness of other vertices and do not need to probe any other incoming edges for $u$ until the next vertex is added to $A$. For a fixed set $A$, both activeness of vertices and validity of certificates are determined and do not change when new probes are made. Only when $A$ is extended and the current certificate of $u$ is no longer valid do we need to look for a new certificate for $u$. A type-1 certificate $v$ becomes invalid when $v$ is added into $A$, while a type-2 certificate $(v_{1},v_{2})$ becomes invalid when $(v_{1}<_{A}v_{2})\lor(v_{2}<_{A}v_{1})$ happens as $A$ expands.

In the worst case, one may need to update the certificates again and again and thus probe too many edges. By checking the validity of certificates in a random order, the worst case is avoided with high probability. We prove that our algorithm uses only $O(n\log n+w)$ probes with high probability in the next subsection, where the term $n\log n$ comes from the probes used in re-searching for valid certificates.

Our algorithm works by repeatedly choose a vertex $u$ which does not have a valid certificate.

1. 1.

   If it is an ideal vertex, we use the strategy mentioned above to determine the direction of edges between $T_{u}$ and $u$, then add $u$ to $A$.

2. 2.

   Otherwise there must be a vertex $v\in T_{u}$ s.t. $v\notin A$, or a pair of vertices $v_{1},v_{2}\in T_{u}$ s.t. $(v_{1},v_{2}\in A)\land(v_{1}\not<_{A}v_{2})\land(v_{2}\not<_{A}v_{1})$. We randomly choose such a vertex $v$ or such a pair of vertices $(v_{1},v_{2})$ and probe the edge(s) between $u$ and them. Then either at least one mis-predicted edge is found, or a valid certificate for $u$ is found.

Since there is always an active vertex $u$, after finding some mis-predicted edges and removing the corresponding wrong in-neighbors from $T_{u}$, $u$ must become an ideal vertex, that is how the algorithm makes progress.

Here is the pseudo code of the algorithm:

We first prove that the algorithm can always proceed, and always terminates.

Now we proceed to analyze the total number of probes made by the algorithm. First we introduce some important lemmas:

Remark. Lemma 3.8 and Corollary 3.10 use the fact that we determine the order among vertices in $T_{u}$ not according to all edges probed till now, but only according to the edges in the induced subgraph $G[A]$. It seems more efficient if we use all the information instead of the restricted portion, but it will create subtle correlations and we do not know how to analyze. The above fixed-order properties are crucial in the proof of our main theorem.

See 1.1