Dasgupta införde nyligen en kostnadsfunktion för hierarkisk klusterering av en uppsättning punkter som ges parvis likheter mellan dem. Han visade att denna funktion är N P - hård för att optimera, men en uppifrån-och-ner rekursiv partitionering heuristic baserat på en α n - approximation algoritm för enhetliga glesaste snitt ger en approximation av O(α n log n) (den nuvarande bästa algoritmen har α n = O ( ε log n)). Vi visar att den tidigare nämnda glesaste skär heuristiska i själva verket får en O (α n ) - approximation. Algoritmen gäller även för en generaliserad kostnadsfunktion som studerats av Dasgupta. Dessutom får vi ett starkt omisskännligt resultat som visar att det hierarkiska klustermålet är svårt att närma sig inom någon konstant faktor om man antar SmallSet Expansion (SSE) Hypotesen. Slutligen diskuterar vi approximationsalgoritmer baserade på konvexa avslappningar. Vi presenterar en spridning metriska SDP avkoppling för problemet och visar att det har integrality gap som mest O ( ε log n). Fördelen med SDP i förhållande till den glesaste skär heuristiska är att det ger en explicit lägre gräns på den optimala lösningen och skulle kunna ge en ännu bättre approximation för hierarkisk klusterbildning. I själva verket tjänade vår analys av denna SDP som inspiration för vår förbättrade analys av den glesaste skär heuristiska. Vi visar också att en spridning metriska LP avkoppling ger en O (log n)-uppskattning.
I synnerhet REF förbättra approximationsfaktorn till O log n genom att visa hur man avrundar en spridningsmetrisk SDP-avslappning för denna kostnadsfunktion.
Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}