Vi anser att problemet med att uppskatta värdet av max skär i en graf i den strömmande modellen av beräkning. På en extrem, det finns en trivial 2- approximation för detta problem som använder endast O (log n) utrymme, nämligen räkna antalet kanter och utdata hälften av detta värde som uppskattningen för max skär värde. På den andra ytterligheten, om man tillåter Õ(n) utrymme, då en nära optimal lösning till det maximala skärvärdet kan erhållas genom att lagra en Õ(n)-storlek sparifierare som i huvudsak bevarar den maximala skärningen. En spännande fråga är om polylogaritmiskt utrymme räcker för att uppnå en icke-trivial approximation till det maximala skärvärdet (dvs. slå faktor 2). Det visades nyligen att problemet med att uppskatta storleken på en maximal matchning i en graf medger en icke-trivial approximation i poly-logaritmiskt utrymme. Vårt huvudsakliga resultat är att alla strömmande algoritmer som bryter 2- approximationsbarriären kräver att utrymme även om kanterna på inmatningskurvan presenteras i slumpmässig ordning. Vårt resultat uppnås genom att visa en fördelning över grafer som antingen är bipartite eller 1 2 - långt från att vara bipartite, och att fastställa att  på plats är nödvändigt för att skilja mellan dessa två fall. Som en direkt följd av detta får vi alltså det utrymme som krävs för att testa om en graf är bipartit eller 1 2 - långt ifrån att vara bipartit. Vi visar också att för alla  och > 0, varje strömmande algoritm som får en (1 +  på)- tillnärmning till max skär värde när kanter anländer i kontradiktorisk ordning kräver n 1-O ( på) utrymme, vilket innebär att  och (n) utrymme är nödvändigt för att få en godtyckligt bra approximation till max skärvärdet.
Oberoende av vårt arbete studerar Kapralov, Khanna och Sudan REF samma problem med att approximera MaxCut i streamingmodellen.
Streaming Lower Bounds for Approximating MAX-CUT
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}