Abstrakt. I semi-streaming modellen, en algoritm får en ström av kanter av en graf i godtycklig ordning och använder ett minne av storlek O(n polylog n), där n är antalet hörn av en graf. I detta arbete presenterar vi semi-streaming algoritmer som utför en eller två passerar över ingångsströmmen för maximal matchning utan begränsningar på inmatningskurvan, och för viktiga specialfall av bipartit grafer som vi kallar Maximum Bipartite Matching. Den Greedy matchande algoritmen utför ett pass över ingång och utgångar en 1/2 approximation. Huruvida det finns en bättre one-pass algoritm har varit en öppen fråga sedan utseendet av den första tidningen om streaming algoritmer för matchande problem 2005 [Feigenbaum et al., SODA 2005]. Vi gör följande framsteg i detta problem: I en-pass-inställningen visar vi att det finns en deterministisk semi-streaming algoritm för maximal Bipartit Matchning med förväntad approximationsfaktor 1/2 + 0,005, förutsatt att kanterna anländer en efter en i (uniform) slumpmässig ordning. Vi utökar denna algoritm till allmänna grafer, och vi får en 1/2 + 0,003 approximation för maximal matchning. I två-pass-inställningen, behöver vi inte den slumpmässiga ankomstordning antagande (kanten ström är i godtycklig ordning). Vi presenterar en enkel randomiserad tvåpass semistreaming algoritm för maximal Bipartite Matching med förväntad approximation faktor 1/2 + 0,019. Dessutom diskuterar vi en mer involverad deterministisk semi-pass semi-streaming algoritm för maximal Bipartite Matchning med approximation faktor 1/2 + 0,019 och en generalisering av denna algoritm till allmänna grafer med approximation faktor 1/2 + 0,0071.
Dock är en bättre algoritm känd under antagandet av slumpmässiga kanter ankomster av REF, som uppnår en 1/2+ approximation för en konstant > 0.
Maximum Matching in Semi-Streaming with Few Passes
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}