En lokal graf partitionering algoritm hittar en uppsättning hörn med liten ledning (dvs. Ett glest snitt) genom att adaptivt utforska en stor graf G, med början från en specificerad vertex. För att algoritmen ska vara lokal, måste dess komplexitet begränsas i termer av storleken på den uppsättning den utdata, med som mest ett svagt beroende av n, antalet hörn i G. Föregående lokala partitionering algoritmer hitta glesa nedskärningar med hjälp av slumpmässiga promenader och personlig PageRank. I det här dokumentet introducerar vi en randomiserad lokal partitioneringsalgoritm som finner en gles skärning genom att simulera den volym-fördjupade evolverande set-processen, som är en Markov kedja på uppsättningar av hörn. Vi bevisar att för alla uppsättningar hörn A som har ledning som mest, och för minst hälften av start hörn i A, vår algoritm kommer att producera (med sannolikhet minst hälften) en uppsättning ledning O(en 1/2 log 1/2 n). Komplexiteten hos en lokal partitioneringsalgoritm mäts med dess arbets-/volymförhållande, vilket är förhållandet mellan algoritmens beräkningskomplexitet på en given körning, och volymen av den inställda utmatningen. Vi bevisar att för vår algoritm, det förväntade värdet av arbets-/volymförhållandet är O(en) −1/2 polylog(n)). Den bästa tidigare lokala partitioneringsalgoritmen, på grund av Andersen, Chung och Lang, har samma approximationsgaranti men ett större arbets-/volymförhållande av O( på −1 polylog(n)). Som en tillämpning av vår lokala partitioneringsalgoritm, konstruerar vi en snabb algoritm för att hitta balanserade nedskärningar. Den resulterande algoritmen tar som indata en graf och ett fast värde av en, har komplexitet (m + n på −1/2 ) · O(polylog(n))), och returnerar en skärning med ledning O(en 1/2 log 1/2 n) och volym minst v  och /2, där v  och är volymen av den största uppsättningen i grafen med ledning som mest.
Andersen och Peres REF simulerar en volymförstärkt och föränderlig set-process för att hitta glesa snitt.
Finding sparse cuts locally using evolving sets
{'venue': "STOC '09", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}