English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the DAG sorting problem: a partial order $\mathcal{P}$ on $n$ keysis to be discovered by querying as few edges of an input graph $G=(V=[n],E)$ aspossible. The graph $G$ only contains edges between ordered pairs, and $G$ ispromised to contain the transitive reduction of the DAG describing$\mathcal{P}$. We present two technical and one conceptual result.  We first show that DAG sorting is closely related to the fundamental problemof sorting with priced information. \emph{Our first technical result} shows theexistence of an algorithm with a $\widetilde{O}(n^{3/4})$ competitive ratio forthe $\{0,1,n,\infty\}$ cost version. Thus the $\Omega(n)$ lower bound formaximum cannot extend to sorting, reopening the question of the existence of a$o(n)$-competitive algorithm for the general version.  \emph{As our main conceptual contribution}, we define a notion ofinstance-optimality for the specific problem of DAG sorting, and also unify theexisting landscape of instance-optimal algorithms for other static problemsexisting in literature. This includes problems like sorting [Estivill-Castroand Woods, ACM Comput. Surv. 1992], convex hull [Afshani, Barbay and Chan, JACM2017], and adaptive joins [Demaine, L\'{o}pez-Ortiz and Munro, SODA 2000]. Ourunified notion of instance-optimality is also related to FPT algorithms andalgorithms with predictions.  We consider the special case of DAG sorting where the input graph isbipartite. \emph{As our second technical result}, we show that a recentalgorithm for bichromatic sorting [Goswami and Jacob, ITCS 2024] gives analgorithm for bipartite DAG sorting which is instance-optimal to a factor$O(\log^{3}n)$. This generalizes the famous nuts-and-bolts problem to thesetting where the number of nuts and bolts are different, and there is nopromise of a matching between them, and the resulting order might not be total.

Unifying Instance Optimality for Static Problems: A Case Study on Sorting a DAG