2026-08-25T18:47:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27176 2026-08-25T13:18:16Z ddc:004 open_access

Adaptive Sparsification for Linear Programming Objois, Etienne Vladu, Adrian linear programming sparsification sampling quantum algorithms We provide a generic toolkit for sparsifying the constraint set of linear programs (LPs). To this end, we reduce solving a linear program with n constraints and d variables (n≫ d), to solving a sequence of LPs defined over only a small subset of the constraints, obtained by adaptively sub-sampling the original set. We provide results for both the low and high precision regimes. To achieve the former result, we streamline and generalize the techniques from [Assadi '25] for approximately computing maximum matchings in the semi-streaming setting to the case of general LPs. For the latter, we robustify the methods of [Clarkson '95], which were originally designed for exact LP solvers. As a consequence we obtain fast approximate LP solvers which reduce the dependence on width and error from quadratic to linear, compared to vanilla multiplicative-weights based approaches. Additionally, we leverage our findings to obtain fast LP solvers in the quantum query access model, where the running time scales with √n. This completely decouples the component responsible for quantum speed-ups, solely represented by a generalization of Grover’s search, from its classical algorithmic counterpart. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Etienne Objois and Adrian Vladu 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.40 urn:nbn:de:0030-drops-271768 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.40 eng https://creativecommons.org/licenses/by/4.0/legalcode