Un algoritmo approssimato per il clustering asimmetrico

This paper describes and analyzes an approximation algorithm for the asymmetric p-center problem, a type of clustering problem where the distance function does not satisfy the symmetry property. This problem, like many other clustering problems, belongs to the class of NP-hard problems, for which no exact algorithms solvable in polynomial time exist. The algorithm discussed, developed by Panigrahy (MIT) and Vishwanathan (IIT Bombay), is the first of its kind capable of providing, in polynomial time, an approximate solution with an approximation factor of O(log*n), where n is the size of the problem. The algorithm consists of two main phases: in the first, called the Find and Halve Phase, a subset of centers, known as CCV (Center Capturing Vertices), are quickly selected to cover part of the set of points within a radius of 2R, where R is the optimal radius. In the second phase, called the Augment Phase, a heuristic for the appropriately formulated Set-Covering problem is used to identify the remaining centers.

Il presente lavoro descrive e analizza un algoritmo approssimato per il problema del p-center asimmetrico, una tipologia di problema di clustering in cui la funzione distanza non soddisfa la proprietà di simmetria. Questo problema, come molti altri problemi di clustering, appartiene alla classe dei problemi NP-hard, per i quali non esistono algoritmi esatti risolvibili in tempo polinomiale. L'algoritmo discusso, sviluppato da Panigrahy (MIT) e Vishwanathan (IIT Bombay), è il primo nel suo genere in grado di fornire, in tempo polinomiale, una soluzione approssimata con fattore di approssimazione O(log*n), dove n è la dimensione del problema. L'algoritmo si articola in due fasi principali: nella prima, detta Fase Find and Halve, viene selezionato rapidamente un sottoinsieme di centri, detti CCV (Center Capturing Vertices), che coprono parte dell'insieme di punti entro un raggio di 2R, dove R è il raggio ottimo. Nella seconda fase, chiamata Fase Augment, si utilizza un'euristica per il problema di Set-Covering opportunamente formulato, per individuare i centri rimanenti.