2026-07-20T05:11:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20192 2024-07-02T07:52:50Z ddc:004 open_access

An Optimal Sparsification Lemma for Low-Crossing Matchings and Its Applications to Discrepancy and Approximations Csikós, Mónika Mustafa, Nabil H. low-crossing matchings uniform sampling discrepancy approximations Matchings with low crossing numbers were originally introduced in the late 1980s in the seminal works of Welzl [Welzl, 1988; Welzl, 1992] and Chazelle-Welzl [Chazelle and Welzl, 1989]. They have since become fundamental structures in combinatorics, computational geometry, and algorithms. In this paper, we study matchings with low crossing numbers and their relation to random samples. In particular, our main technical result states that, given a set system (X, 𝒮) with dual VC-dimension d and a parameter α ∈ (0, 1], a random set of Θ̃(n^{1+α}) edges of binom(X,2) contains a linear-sized matching with crossing number O (n^{1-α/d}). Furthermore, we show that this bound is optimal up to a logarithmic factor. By incorporating the above sampling step to existing algorithms, we obtain improved running times, by a factor of Θ̃(n), for computing matchings with low crossing numbers. This immediately implies new bounds for a number of well-studied problems, such as combinatorial discrepancy, ε-approximations and their applications. To the best of our knowledge, these are the first near-linear time algorithms for general, non-geometric set systems, for a) matchings with sub-linear crossing numbers, and b) discrepancy beating the standard deviation bound. As an immediate consequence we get fast algorithms for computing o(1/ε²)-sized ε-approximations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mónika Csikós and Nabil H. Mustafa 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.49 urn:nbn:de:0030-drops-201925 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.49 eng https://creativecommons.org/licenses/by/4.0/legalcode