Sorting under partial (interval order) information

In this paper we study how to efficiently order a set of imprecise points. In one dimension, the order of a set of points is their sorted order from low to high. A set of imprecise points in the preprocessing model consists of a set of $n$ uncertainty regions $\mathcal{R} = \{R_1, R_2, \ldots R_n \}$ and a set of $n$ points $P = \{ p_1, p_2, \ldots p_n\}$ such that for every $R_i \in \mathcal{R}$ there is an associated point $p_i \in P$ with $p_i \in P$. In one dimension, the set $\mathcal{R}$ is a set of intervals which induces a partial order such that the total order of the underlying true points $P$ extends that partial order. We show how to preprocess the partial order induced by $\mathcal{R}$, such that given the point set $P$ we can uncover the underlying total order in uncertainty-region optimal time. Specifically, we parametrize the degree of overlap by the intervals with a measure we call the ambiguity of the set $\mathcal{R}$ and we show that the ambiguity of $\mathcal{R}$ is a lower bound for the time required to sort the points $P$. This paper can be seen as a geometric variant of sorting under partial information, which is a well-studied topic within computer science.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.