Vi ger en ny spektral approximationsalgoritm för det balanserade (edge-)separator problemet som, med tanke på en graf G, en konstant balans b  på 0, 1/2] och en parameter γ, antingen finner en utgång ett certifikat som alla b-balanserade nedskärningar i G har ledning åtminstone γ, och körs i tid Õ(m). Detta avgör frågan om att utforma asymptotiskt optimala spektralalgoritmer för balanserad avskiljare. Vår algoritm bygger på en variant av värmekärnans slumpmässiga gång och kräver, som en subrutin, en algoritm för att beräkna exp(−L)v där L är Laplacian av en graf relaterad till G och v är en vektor. Algoritmer för beräkning av matris-exponentiell-vektor produkten utgör effektivt vår nästa uppsättning av resultat. Vårt huvudsakliga resultat här är en ny algoritm som beräknar en bra approximation till exp(−A)v för en klass av symmetriskt positiv semidefinit (PSD) matriser A och en given vektor v, i tiden grov o(m A), oberoende av normen i A, där mA är antalet icke-noll poster i A. Detta använder, på ett icke-trivialt sätt, resultatet av Spielman och Teng på inverterande symmetriska och diagonalt dominanta matriser i Õ(m A) tid. Slutligen, med hjälp av gamla och nya enhetliga approximationer till e −x visar vi hur man, via Lanczos-metoden, får en enkel algoritm att beräkna exp(−A)v för symmetriska PSD-matriser som löper i tiden ungefär O(t A · A ), där tA är den tid som krävs för beräkning av vektorn Aw för given vektor w. Som en applikation får vi en enkel och praktisk algoritm, med utgångsledning O( ε γ), för balanserad avskiljare som körs i tid Õ( m / ε γ). Denna sistnämnda algoritm matchar drifttiden, men förbättrar den approximativa garantin för den Evolving-Sets-baserade algoritmen av Andersen och Peres för balanserad avskiljare.
Orecchia m.fl. använda en variant av värmekärnan slumpmässiga promenader i sin randomiserade algoritm för att beräkna ett snitt i en graf med föreskrivna balans begränsningar REF.
Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator
{'venue': "STOC '12", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}