2026-07-23T19:19:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21124 2024-09-23T09:13:17Z ddc:004 open_access

Semi-Streaming Algorithms for Weighted k-Disjoint Matchings Ferdous, S M Samineni, Bhargav Pothen, Alex Halappanavar, Mahantesh Krishnamoorthy, Bala Matchings Semi-Streaming Algorithms Approximation Algorithms We design and implement two single-pass semi-streaming algorithms for the maximum weight k-disjoint matching (k-DM) problem. Given an integer k, the k-DM problem is to find k pairwise edge-disjoint matchings such that the sum of the weights of the matchings is maximized. For k ≥ 2, this problem is NP-hard. Our first algorithm is based on the primal-dual framework of a linear programming relaxation of the problem and is 1/(3+ε)-approximate. We also develop an approximation preserving reduction from k-DM to the maximum weight b-matching problem. Leveraging this reduction and an existing semi-streaming b-matching algorithm, we design a (1/(2+ε))(1 - 1/(k+1))-approximate semi-streaming algorithm for k-DM. For any constant ε > 0, both of these algorithms require O(nk log_{1+ε}² n) bits of space. To the best of our knowledge, this is the first study of semi-streaming algorithms for the k-DM problem. We compare our two algorithms to state-of-the-art offline algorithms on 95 real-world and synthetic test problems, including thirteen graphs generated from data center network traces. On these instances, our streaming algorithms used significantly less memory (ranging from 6× to 512× less) and were faster in runtime than the offline algorithms. Our solutions were often within 5% of the best weights from the offline algorithms. We highlight that the existing offline algorithms run out of 1 TB memory for most of the large instances (> 1 billion edges), whereas our streaming algorithms can solve these problems using only 100 GB memory for k = 8. Schloss Dagstuhl – Leibniz-Zentrum für Informatik S M Ferdous and Bhargav Samineni and Alex Pothen and Mahantesh Halappanavar and Bala Krishnamoorthy 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.53 urn:nbn:de:0030-drops-211245 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.53 eng https://creativecommons.org/licenses/by/4.0/legalcode