Tänk på följande kommunikationsproblem. Alice har en graf GA = (P, Q, EA) och Bob har en graf GB = (P, Q, EB), där  och P  till =  på Q till = n. Alice får skicka Bob ett meddelande m som bara beror på grafen GA. Bob måste sedan skriva ut en matchande M  på EA EB. Vilken är den minsta meddelandestorleken på meddelandet m som Alice skickar till Bob som gör det möjligt för Bob att återställa en matchning av storlek minst (1 − ) gånger den maximala matchningen i GA  på GB? Den minsta meddelandelängden är en omgångskommunikationens komplexitet genom att approximera tvåpartsmatchning. Det är lätt att se att en rund kommunikation komplexitet ger också en lägre gräns på det utrymme som behövs av en one-pass streaming algoritm för att beräkna en (1 − )-ungefärlig bipartite matchning. Fokus för detta arbete är att förstå en-round kommunikations komplexitet och en-pass streaming komplexitet av maximal bipartite matchning. I synnerhet, hur väl kan man approximera dessa problem med linjär kommunikation och utrymme? Före vårt arbete var bara en 12 - approximation känd för båda dessa problem. För att studera dessa frågor, introducerar vi begreppet en -matchning omslag av en bipartit graf G, som är en gles subgraph av den ursprungliga grafen som bevarar storleken på maximal matchning mellan varje delmängd av hörn till inom en additiv n fel. Vi ger en polynom tid konstruktion av en 1 2 -matchning omslag av storlek O (n) med några avgörande ytterligare egenskaper, vilket visar att Alice och Bob kan uppnå en 2 3 - approximation med ett meddelande av storlek O (n). Även om vi inte tillhandahåller gränser på storleken på -matchning täcker för < 1/2, vi bevisar att i allmänhet, storleken på den minsta -matchning omslag av en graf G på n hörn är i huvudsak lika med storleken på den största så kallade -Ruzssa Szemerédi graf på n hörn. Vi använder denna anslutning för att visa att för alla δ > 0, a ( 2 3 + δ) - tillnärmning kräver en kommunikation komplexitet n 1 + på (1/ log log n). Vi anser också att den naturliga begränsningen av problemet där GA och GB bara får dela hörn på ena sidan av bipartitionen, som motiveras av applikationer till en-pass streaming med vertex ankomster. Vi visar att en 3 4 - approximation kan uppnås med en linjär storlek budskap i detta fall, och detta resultat är bäst möjligt i att super-linjära utrymme behövs för att uppnå en bättre approximation. Slutligen bygger vi på våra tekniker för den begränsade versionen ovan för att designa one-pass streaming algoritm för fallet när hörn på ena sidan är kända i förväg, och hörnen på den andra sidan anländer på ett strömmande sätt tillsammans med alla sina incidenter kanter. Detta är just inställningen av den berömda (1 − 1 e )-konkurrenskraftiga randomiserade algoritm av Karp-Vazirani-Vazirani (KVV) för online bipartite matchning problem [12]. Vi presenterar här den första deterministiska en-pass streaming (1 − 1 e) - approximation algoritm med O(n) utrymme för denna inställning.
KVV-algoritmen kan också implementeras som en O(n log n) rymd randomiserad semistreamingalgoritm medan Goel el al REF visar att det finns en deterministisk semistreamingalgoritm med hjälp av endast O(n) utrymme som tydligt fastställer kraften i semistreamingmodellen.
On the communication and streaming complexity of maximum bipartite matching
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}