2026-07-21T03:11:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18140 2024-03-06T11:01:07Z ddc:004 open_access

Space-Efficient Interior Point Method, with Applications to Linear Programming and Maximum Weight Bipartite Matching Liu, S. Cliff Song, Zhao Zhang, Hengjie Zhang, Lichen Zhou, Tianyi Convex optimization interior point method streaming algorithm We study the problem of solving linear program in the streaming model. Given a constraint matrix A ∈ ℝ^{m×n} and vectors b ∈ ℝ^m, c ∈ ℝ^n, we develop a space-efficient interior point method that optimizes solely on the dual program. To this end, we obtain efficient algorithms for various different problems: - For general linear programs, we can solve them in Õ(√n log(1/ε)) passes and Õ(n²) space for an ε-approximate solution. To the best of our knowledge, this is the most efficient LP solver in streaming with no polynomial dependence on m for both space and passes. - For bipartite graphs, we can solve the minimum vertex cover and maximum weight matching problem in Õ(√m) passes and Õ(n) space. In addition to our space-efficient IPM, we also give algorithms for solving SDD systems and isolation lemma in Õ(n) spaces, which are the cornerstones for our graph results. Schloss Dagstuhl – Leibniz-Zentrum für Informatik S. Cliff Liu and Zhao Song and Hengjie Zhang and Lichen Zhang and Tianyi Zhou 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.88 urn:nbn:de:0030-drops-181408 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.88 eng https://creativecommons.org/licenses/by/4.0/legalcode