Vi utformar en generisk metod för att minska uppgiften att hitta viktade matchningar till att hitta korta förstärkningsvägar i oviktade grafer. Denna metod gör det möjligt för oss att tillhandahålla effektiva implementationer för approximering av viktade matchningar i streamingmodellen och i den massivt parallella beräkningsmodellen (MPC). I samband med streaming med slumpmässiga kanter, ger våra tekniker en ( 1 /2+c)-tillnärmningsalgoritm som bryter den naturliga barriären på 1 /2. För multi-pass streaming och MPC-modellen, visar vi att varje algoritm computing a (1 − δ)-ungefärlig oviktad matchning i bipartit grafer kan översättas till en algoritm som beräknar en (1 − ε(ε))-ungefärlig maximal viktad matchning. Dessutom har denna översättning endast en konstant faktor (som beror på ε > 0) overhead i komplexiteten. Direktionera detta med de nuvarande bästa multi-pass streaming och MPC algoritmer för oviktade matchningar ger följande resultat för maximal viktade matchningar: • A (1 - ε) - approximation streaming algoritm som använder Oε(1) passerar 1 och Oε(n poly(log n)) minne. Detta är den första (1 − ε) - approximation strömmande algoritm för viktade matchningar som använder ett konstant antal passer (endast beroende på ε). • A (1 − ε)-tillnärmningsalgoritm i MPC-modellen som använder Oε(log log n) rundor, O(m/n) maskiner per runda, och Oε(n poly(log n)) minne per maskin. Detta förbättrar den tidigare bästa approximationsgarantin på ( 1 /2 - ε) för viktade grafer.
Ett nyligen utfört arbete av Gamlath et al. REF visar att när kanterna anländer i en slumpmässig ordning, finns det en semi-streaming algoritm som finner en 1/2 + 1 approximation av den maximala viktade matchning, slå 1/2 barriären för det viktade fallet.
Weighted Matchings via Unweighted Augmentations
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}