It is shown that up to logarithmic factors, generalized sorting is no harder than ordinary sorting, and a randomized algorithm is given that uses $O(n \log^4 n)$ comparisons in expectation.
Abstract
We continue the study of the classic \emph{generalized sorting problem}, a basic variant of ordinary sorting. There are $n$ elements and an (initially hidden) total ordering $\pi$ over them. Unlike in ordinary sorting, however, only \emph{some} comparisons are allowed: those given by the edges of an undirected graph $G = (V, E)$ on the elements. How many comparisons are needed to find the total ordering? In ordinary sorting, $\Theta(n \log n)$ comparisons are necessary and sufficient. For generalized sorting, however, the best known upper bound has been $\tilde{O}(n^{3/2})$ since the work of Huang, Kannan, and Khanna (FOCS 2011), who even asked whether the problem might in fact require $n^{1+\Omega(1)}$ comparisons. We show that it does not: we give a randomized algorithm that uses $O(n \log^4 n)$ comparisons in expectation. Thus, up to logarithmic factors, generalized sorting is no harder than ordinary sorting.
We study the generalized sorting problem where only a subset of the pairs can be compared. Equivalently, we are given an $n$-vertex $m$-edge graph $G=(V, E)$ where the vertex set $V$ is to be sorted, and the edge set $E$ indicates possible comparisons. The goal is to sort $V$ with as few (adaptive) queries to $E$ as po...
Online sorting asks how to place $n$ sequentially arriving elements in an array to minimize the sum of absolute differences between consecutive elements. Fully-dynamic sorting further extends the problem to allow both element insertions and deletions. Without recourse, these problems face strong lower bounds on the com...
We give a deterministic algorithm for finding a subset of the input integers $1\le a_1,\ldots,a_n \le \Delta$ that sums to the target $t$ in $\mathcal{O}(n+\Delta^{1+o(1)})$ time. This improves upon the previous $\widetilde{\mathcal{O}}(n + \Delta^{1.5})$-time algorithm by Chen, Lian, Mao, and Zhang (SODA 2024), and ac...
We study elitist randomized local search for sorting permutations. In this model, each iteration considers a possible exchange of two positions. The entries are exchanged if and only if they are in the wrong order. We introduce \emph{distance-unbiased} selection rules, which may choose an arbitrary distribution over ex...
We show that if an $(n,d,\lambda)$-graph satisfies $\lambda\leq (1-\delta)d$ and $d\gg \delta^{-6}(\log n)^{3}$ for some $\delta>0$, then it is Hamiltonian. A qualitatively similar result was recently proven by Brada\v{c} and Janzer. Our proof here is shorter and gives better quantitative bounds. \par In our proof, as...
The total $\{k\}$-domination problem ($T\{k\}DP$) seeks a minimum-weight function such that the sum of weights in every open neighborhood is at least $k$. While this problem is known to be NP-hard for general graphs, we demonstrate that for the family of caterpillars, it simplifies to the classical total domination num...
M. Escalante, Paola B. Tolomei, María Inés Lopez Pujato· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.