2026-07-20T11:16:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24744 2026-01-21T09:56:23Z ddc:004 open_access

The Exchange Problem Garg, Mohit Sarswat, Suneel Exchanges Double Auctions Matching Algorithms Element Distinctness Time Complexity Auctions are widely used in exchanges to match buy and sell requests. Once the buyers and sellers place their requests, the exchange determines how these requests are to be matched. The two most popular objectives used while determining the matching are maximizing volume with dynamic pricing and maximizing volume at a uniform price. In this work, we study the algorithmic complexity of the problems arising from these matching tasks. For dynamic-price matching, we establish a lower bound of Ω(n log n) on the running time, thereby proving that the currently best-known O(n log n) algorithm is time-optimal. In contrast, for uniform-price matching, we present a linear-time algorithm, improving upon previous methods that require O(n log n) time to match n requests. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mohit Garg and Suneel Sarswat 2025 Is Part Of LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AFT.2025.25 urn:nbn:de:0030-drops-247449 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.25 eng https://creativecommons.org/licenses/by/4.0/legalcode