Vi presenterar en allmän metod för att designa snabba approximationsalgoritmer för skär-baserade minimeringsproblem i oriktade grafer. I synnerhet utvecklar vi en teknik som med tanke på alla sådana problem som kan approximeras snabbt på träd, gör det möjligt att approximera det nästan lika snabbt på allmänna grafer medan bara förlora en poly-logaritmisk faktor i approximationsgarantin. För att illustrera tillämpligheten av vårt paradigm, fokuserar vi vår uppmärksamhet på det oriktade glesaste skär problemet med allmänna krav och det balanserade separator problemet. Genom en enkel användning av vårt ramverk får vi polylogaritmiska approximeringsalgoritmer för dessa problem som löper i tiden nära linjära. Huvudverktyget bakom vårt resultat är ett effektivt förfarande som bryter ner allmänna grafer till enklare grafer samtidigt som skärningsstrukturen i stort sett bevaras. Denna nedbrytning är inspirerad av den cut-based graf sönderdelningen av Räcke som utvecklades i samband med glömska routing system, liksom, av konstruktionen av ultrasparsifierare på grund av Spielman och Teng som användes för att förkonditionera symmetriskt diagonalt dominerande matriser. Den fångade av ovan nämnda problem uppgift att dela upp en graf i relativt stora bitar medan minimera antalet kanter skär är ett grundläggande kombinatoriska problem (se [1] ) med en lång historia av
Informellt en hierarkisk nedbrytning av en graf G är en uppsättning träd för vilka bladen motsvarar hörnen av G, och för vilka strukturen av deras nedskärningar ungefär motsvarar nedskärningarna i G. Graph nedbrytningar har studerats i samband med glömska routing system (se REF för en undersökning).
Fast Approximation Algorithms for Cut-Based Problems in Undirected Graphs
{'venue': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'journal': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}