I detta papper presenterar vi förbättrade gränser för approximering av maximal matchning i bipartite grafer i den strömmande modellen. För det första överväger vi frågan om hur väl maximal matchning kan approximeras i ett enda pass över inmatningen när Õ(n) utrymme är tillåtet, där n är antalet hörn i inmatningskurvan. Två naturliga varianter av detta problem har beaktats i litteraturen: 1) kanten ankomst inställning, där kanterna anländer i strömmen och (2) vertex ankomst inställning, där hörn på ena sidan av grafen anländer i strömmen tillsammans med alla deras incident kanter. Den senare inställningen har också studerats ingående i samband med online-algoritmer, där varje ankommande vertex måste antingen matchas oåterkalleligt eller kasseras vid ankomst. I online-inställningen uppnår den berömda algoritmen KarpVazirani-Vazirani en 1 – 1/e approximation genom att på ett avgörande sätt använda randomisering (och med Õ(n) utrymme). Trots att den strömmande modellen är mindre restriktiv genom att algoritmen inte begränsas till att matcha hörn oåterkalleligt vid ankomst, är den mest kända approximationen i den strömmande modellen med vertex ankomster och Õ(n) utrymme samma faktor 1 − 1/e. Vi visar att ingen (eventuellt randomiserad) streamingalgoritm som begränsas till att använda Õ(n) utrymme kan uppnå en bättre än 1 − 1/e approximation till maximal matchning, även i vertex ankomst inställning. Detta leder till den slående slutsatsen att ingen enstaka pass streaming algoritm kan få någon fördel jämfört med online-algoritmer om det inte använder betydligt mer än Õ(n) utrymme. Dessutom ger vår bundna den mest kända omöjligheten resultat för approximering av matchningar i kanten ankomst modell (förbättra på gränsen 2/3 bevisas av Goel på al [SODA'12]). För det andra, vi anser problemet med att approximera matchningar i flera pass i vertex ankomst inställning. Vi visar att en enkel lastbalanseringsmetod i bråk ger ett ungefärligt förhållande + o(1/k) i k-pass med linjärt utrymme. Således uppnår vår algoritm bästa möjliga 1 − 1/e approximation i ett enda pass och förbättrar på 1 − O( log k/k) approximation i k pass på grund av Ahn och Guha [ICAP'11]. Dessutom ger vårt tillvägagångssätt en effektiv lösning på det problem med Gap-existens som Charles et al [EC'10].
På den nedre gränsen kan maximal matchning inte approximeras bättre än e/e – 1) – 1,58 faktor REF i semistreamingmodellen.
Better bounds for matchings in the streaming model
{'venue': None, 'journal': 'arXiv: Data Structures and Algorithms', 'mag_field_of_study': ['Computer Science', 'Mathematics']}