I den här artikeln anser vi att grafalgoritmer i modeller av beräkning där rymdanvändning (slumpvis tillgänglig lagring, förutom skrivskyddad ingång) är sublinjär i antalet kanter m och tillgången till indata begränsas. Dessa frågor uppstår i många naturliga miljöer, och i synnerhet i analysen av strömmande algoritmer, MapReduce eller liknande algoritmer, eller meddelande passerar distribuerad dator att modellen begränsade parallellism med sublinjär central bearbetning. Vi fokuserar på viktad nonbipartite maximal matchning i denna artikel. För varje konstant p > 1 ger vi en iterativ provtagningsbaserad algoritm för att beräkna en (1 − ε )-tillnärmning av den viktade nonbipartite maximal matchning som använder O (p/ε ) rundor av provtagning, och O (n 1+1/p ) utrymme. Resultaten sträcker sig till b-matchning med små förändringar. Denna artikel kombinerar adaptiv skisslitteratur och snabba primal-dual algoritmer baserade på avslappnade Dantzig-Wolfe beslutsförfaranden. Varje provtagningsrunda genomförs genom linjära skisser och kan utföras i en enda omgång streaming eller två rundor MapReduce. Artikeln visar också att icke-standard linjära lättnader av ett problem, särskilt straffbaserade formuleringar, är till hjälp för att minska adaptivt beroende av iterationer. efterföljande iterationer. Beräkningen vid en viss omgång beror på beräkningen i tidigare omgångar och därmed är algoritmerna adaptiva. Förekomsten av sådana konstant runda iterativa nära-optimala algoritmer är vanligtvis inte känd för många kombinatoriska optimeringsproblem. Vi noterar att många av dessa distribuerade iterativa datormiljöer, till exempel streaming, MapReduce och dess varianter, och meddelande passerar distribuerade algoritmer, skiljer sig avsevärt i sina detaljer. Medan de flesta algoritmer fokuserar på specifika modeller, större abstraktioner som spänner över flera modeller är inte lätt tillgängliga. I samband med denna artikel använder vi det faktum att miljöer som är allmänt antagna normalt tillåter provtagning och beräkning av inre produkter med pseudorandom vektorer (linjära skisser). Dessutom har hänsynen till beräkningsmiljöer under särskilda resursbegränsningar som kommunikation, utrymme eller tillgång till data inte behandlats i någon större utsträckning vid modellering av kombinatoriska optimeringsproblem. Vi är ofta kvar med formuleringar som var utformade för en annan beräkningsmiljö i åtanke. Nonbipartite matchning har länge varit en standard bärare av kombinatoriska optimeringsproblem. I den här artikeln fokuserar vi på viktade nonbipartite maximal b-matchning problem och utforma nya avkopplingar som är användbara för resurs-konstruerade modeller. På en hög nivå kan vår algoritm ses som en rekursiv provtagningsalgoritm. I varje iteration omdefinierar vi datapunkternas vikter med hjälp av funktioner som är effektiva för att representera, kommunicera och beräkna. På en mer teknisk nivå använder vi internproduktbaserad provtagning så att vi kan minska algoritmens anpassningsförmåga, och därmed antalet iterationer i jämförelse med standard iterativa metoder för att lösa dessa problem. En provtagningsbaserad algoritm för att hitta kanterna i en maximal matchning är naturlig och intuitiv: vi iterativt prov kanter; vi visar att de provade kanterna innehåller en stor matchning eller vi förfina vikterna och upprepa. Även om beskrivningen på hög nivå är naturlig, är detaljerna i analysen, till exempel demonstrationen av en stor matchning eller förfining av vikter, i bästa fall inte uppenbara. I ett nyligen resultat (Lattanzi et al. 2011), Det visades att för en n node m kant graf, Vi kan hitta en O (1) approximation för bipartit grafer med hjälp av O (p) rundor av kantfiltrering via Mapreduce och O (n 1+1/p ) centraliserad utrymme (för alla konstant p > 1). Det visades dock också att den tillnärmning som uppnåddes vid det faktiska genomförandet var bättre än det värsta. Detta väcker den naturliga frågan: är en (1 − ε ) - approximation för någon konstant ε > 0 uppnås i ett litet antal rundor? I den här artikeln tillhandahåller vi en sådan algoritm. Observera att även om vi diskuterar matchningar är dessa frågor tillämpliga på en bredare uppsättning problem; i många scenarier konvergerar iterativa algoritmer snabbare och bättre än vad som bedöms i värsta fall garantier. Tyvärr finns det få systematiska tekniker som tillåter oss att analysera iterativa algoritmer. Ett välkänt exempel är linjär (eller konvex) programmering-och för maximal viktad matchning det finns LP avkopplingar som är exakt. Därför måste varje algoritm som tillhandahåller en (1 − ε ) approximation också (eventuellt implicit) ge en gräns för den underliggande LP, som anges i definition 1. I detta enkla exempel kan vi ställa in z U = 10ε och x i = 1 − 10ε för vertex vid apex. Det är oklart om sådana omfördelningar finns i en stor graf. Och även för oviktade grafer, notera att n 1/δ olika z U påverkar en enda kant och bredden är stor. Ses på ett annat sätt, om en problemdefinition kräver en begränsningsmatris av storlek n 1/ε × m och vi vill lösa det problemet i o(m, n 1/ε ) utrymme och konstant antal rundor, då enkla omvandlingar inte räcker och nyare idéer är nödvändiga. Matchning har studerats väl i samband med streamingalgoritmer. I en sådan inställning motsvarar inmatningen en sekvens av kanter och tillhörande vikter (i, j, w i j ), i godtycklig ordning, och det slumpmässiga åtkomstminnet (RAM) är sublinjär i ingångsstorleken. Beräkningen sker i förbigående. Algoritmen mäts vanligtvis på hur nära utgångslösningen till den optimala lösningen ( dess approximationsförhållande), mängden minne, och antalet passs-mindre är mer önskvärt i alla dessa åtgärder. Observera att iterativ provtagning eller skissning är lätt att beräkna i den strömmande modellen. För viktad nonbipartite matchning var inget tidigare resultat känt i den strömmande modellen där antalet iterationer är oberoende av problemparametrarna. För oviktad kardinalitetsmatchning gav McGregor (2005) en algoritm med 2 O (1/ε ) iterationer med Õ (n) utrymme (där vi ignorerar polylogaritmiska faktorer och polynom beroende av 1/ε) i denna modell. De mest kända singel-round resultat som faktiskt producerar en matchning är en O (1) approximation med hjälp av en enda runda (Eggert et al. Europaparlamentets och rådets förordning (EU) nr 182/2011 av den 16 februari 2011 om fastställande av allmänna regler och principer för medlemsstaternas kontroll av kommissionens utövande av sina genomförandebefogenheter (EUT L 55, 28.2.2011, s. 2010; Feigenbaum et al. 2005; Zelke 2008), som gäller både bipartit och nonbipartite grafer. För bipartit grafer a (1 - ε ) - approximation i O (ε − 2 log 1 ε ) rundor (Ahn och Guha 2013) och en (1 - ε ) approximation i O (ε − 2 ) rundor i en vertex ankomst modell (förutsatt ordning på listan över inmatningskanter) (Kapralov 2013) var kända. I Guruswami och Onak (2013) visas det att ett utrymme som är bundet till n 1+ ska(1/p ) /p O (1) är nödvändigt för ett p-runda kommunikationsprotokoll för att hitta det exakta maximumet i bipartit grafer. En annan välstuderad modell är den kartreducerade modellen med lite centraliserad lagring. Beräkningen fortskrider genom att använda kartan och minska operatörerna i godtycklig ordning av kanterna. Kartoperationen är en enhetlig åtgärd som tillämpas på alla kanter för att dela upp dem. Minska operatören gäller för varje partition och producerar en liten mängd information, som skickas tillbaka till den centrala samordnaren (se Lattanzi et al. (2011) och hänvisningar där). Iterativ provtagning eller skissning är inte svårt att uppnå i denna modell. approximationen för bipartit/nonbipartite grafer med hjälp av O (p) provtagningsrundor och Õ (n 1+1/p ) utrymme i Lattanzi et al. (2011) motsvarar iterativ provtagning (och filtrering). För bipartitdiagram kan approximering uppnås med hjälp av flera algoritmer (se Bahmani et al. (2014) ), men de kräver  och (log n) rundor. Matchning har också studerats i samband med distribuerad databehandling (se Mansour och Vardi (2013) för en resultatundersökning). Den överbelastade kliquemodellen (Drucker et al. 2014) är av intresse för denna artikel; i den modellen, n deltagarna har lokala (eventuellt delade indata) och varje nod kan skicka ett meddelande med begränsad längd till någon annan nod i en runda. Resultaten i denna artikel är följande: i) ett resultat av rumseffektiv beräkning av matchningar ii) en förfining av begreppet anpassningsförmåga till "adaptivitet vid provtagning" och "adaptivitet vid användning",
På samma sätt kräver resultaten av Ahn och Guha REF att n 1+ och 1) utrymme per maskin för att beräkna en O(1)-ungefärlig maximal vikt matchning i ett konstant antal rundor och inte innebär en liknande gräns för linjärt utrymme.
Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching under Resource Constraints
{'venue': 'TOPC', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}