2026-07-25T15:02:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19584 2024-03-06T11:04:24Z ddc:004 open_access

An Algorithm for Bichromatic Sorting with Polylog Competitive Ratio Goswami, Mayank Jacob, Riko Sorting Priced Information Nuts and Bolts The problem of sorting with priced information was introduced by [Charikar, Fagin, Guruswami, Kleinberg, Raghavan, Sahai (CFGKRS), STOC 2000]. In this setting, different comparisons have different (potentially infinite) costs. The goal is to find a sorting algorithm with small competitive ratio, defined as the (worst-case) ratio of the algorithm’s cost to the cost of the cheapest proof of the sorted order. The simple case of bichromatic sorting posed by [CFGKRS] remains open: We are given two sets A and B of total size N, and the cost of an A-A comparison or a B-B comparison is higher than an A-B comparison. The goal is to sort A ∪ B. An Ω(log N) lower bound on competitive ratio follows from unit-cost sorting. Note that this is a generalization of the famous nuts and bolts problem, where A-A and B-B comparisons have infinite cost, and elements of A and B are guaranteed to alternate in the final sorted order. In this paper we give a randomized algorithm InversionSort with an almost-optimal w.h.p. competitive ratio of O(log³ N). This is the first algorithm for bichromatic sorting with a o(N) competitive ratio. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mayank Goswami and Riko Jacob 2024 Is Part Of LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2024.56 urn:nbn:de:0030-drops-195843 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.56 eng https://creativecommons.org/licenses/by/4.0/legalcode