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/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

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

Zendy Tools

Zendy Open

We generalize the classical nuts and bolts problem to a setting where theinput is a collection of $n$ nuts and $m$ bolts, and there is no promise of anymatching pairs. It is not allowed to compare a nut directly with a nut or abolt directly with a bolt, and the goal is to perform the fewest nut-boltcomparisons to discover the partial order between the nuts and bolts. We termthis problem \emph{bipartite sorting}.  We show that instances of bipartite sorting of the same size exhibit a widerange of complexity, and propose to perform a fine-grained analysis for thisproblem. We rule out straightforward notions of instance-optimality as beingtoo stringent, and adopt a \emph{neighborhood-based} definition. Our definitionmay be of independent interest as a unifying lens for instance-optimalalgorithms for other static problems existing in literature. This includesproblems like sorting (Estivill-Castro and Woods, ACM Comput. Surv. 1992),convex hull (Afshani, Barbay and Chan, JACM 2017), adaptive joins (Demaine,L\'{o}pez-Ortiz and Munro, SODA 2000), and the recent concept of universaloptimality for graphs (Haeupler, Hlad\'ik, Rozho\v{n}, Tarjan and T\v{e}tek,2023).  As our main result on bipartite sorting, we give a randomized algorithm thatis within a factor of $O(\log ^3 (n+m))$ of being instance-optimal w.h.p., withrespect to the neighborhood-based definition.  As our second contribution, we generalize bipartite sorting to DAG sorting,when the underlying DAG is not necessarily bipartite. As an unexpectedconsequence of a simple algorithm for DAG sorting, we rule out a potentiallower bound on the widely-studied problem of \emph{sorting with pricedinformation}, posed by (Charikar, Fagin, Guruswami, Kleinberg, Raghavan andSahai, STOC 2000).

On Instance-Optimal Algorithms for a Generalization of Nuts and Bolts and Generalized Sorting