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

Mayank Goswami, Riko Jacob

We generalize the classical nuts and bolts problem to a setting where the input is a collection of $n$ nuts and $m$ bolts, and there is no promise of any matching pairs. It is not…