K-center

Il problema k -centre ( problema k -center in inglese) è un problema di ottimizzazione combinatoria , una branca dell'algoritmo . Il problema può essere descritto in modo informale come segue: date n città, è necessario aprire una caserma dei pompieri in k città, in modo tale da ridurre al minimo la distanza tra ogni città e la stazione dei vigili del fuoco più vicina.

Più formalmente, si tratta, dato un insieme di punti V , di scegliere un sottoinsieme di k punti, chiamati centri, in modo tale che il massimo delle distanze dai punti di V al centro più vicino sia minimizzato. Nella maggior parte dei casi si considera implicitamente che lo spazio sia metrico , il problema viene poi espresso naturalmente come problema su un grafo i cui bordi hanno pesi che rispettano la disuguaglianza triangolare .

Questo problema è studiato principalmente dal punto di vista dell'approssimazione . Esistono diverse varianti, con metriche particolari o altri costi da minimizzare. Un'applicazione diversa dal posizionamento dell'installazione è il partizionamento dei dati (clustering) .

Definizione formale

Il problema è espresso come segue nel caso metrico.

Dato un intero k e un grafo completo non orientato G = ( V , E ), la distanza d ( v i , v j ) ∈ N rispetto alla disuguaglianza del triangolo, trova un sottoinsieme S ⊆ V con | S | = K che riduce al minimo: . In altre parole, consideriamo il problema di ottimizzazione la cui funzione obiettivo è . $\ max _ {{v \ in V}} \ min _ {{s \ in S}} d (v, s)$ $\ min _ {{S \ subseteq V: | S | = k}} \ max _ {{v \ in V}} \ min _ {{s \ in S}} d (v, s)$

Il caso generale senza metrica è poco studiato perché troppo difficile anche dal punto di vista dell'approssimazione. Più precisamente, senza supposizioni il problema non è in APX . Il resto dell'articolo tratta implicitamente il caso metrico.

Complessità

Il problema è NP-completo nella sua versione del problema decisionale .

Approssimazione

Esistono algoritmi di approssimazione del rapporto 2 e se P è diverso da NP questo risultato è ottimale.

Algoritmo avido

Il seguente algoritmo avido è stato proposto da Gonzalez nel 1985. A volte è chiamato primo attraversamento più lontano .

Scegli un primo vertice arbitrario e rendilo un centro.
Fai k-1 volte:
- Trova un vertice la cui distanza dai centri già aperti sia massima
- Rendilo un centro.

La soluzione calcolata è nel caso peggiore, la metà della soluzione ottimale. Lo dimostriamo rapidamente. Alla fine dell'algoritmo, sia r la distanza massima da un punto a un centro e sia p tale punto. Sia S l'insieme costituito da centri e p . L'insieme S ha k + 1 punti almeno r l' uno dall'altro. Quindi nella soluzione ottima, almeno due punti di S devono condividere lo stesso centro (ci sono più punti in S che centri nella soluzione ottima). Secondo la disuguaglianza triangolare, almeno uno di questi punti che condividono lo stesso centro si trova a una distanza r / 2 da un centro.

La complessità temporale dell'algoritmo è O (nk) .

Metodo di soglia

Possiamo ottenere un'approssimazione 2 con il metodo della soglia ( chiamato anche potatura parametrica ). Consiste nel testare tutte le possibili soluzioni: il valore ottimale essendo un costo presente su uno spigolo, il numero di spigoli è polinomiale e possiamo fare un test polinomiale per ogni valore. Il test consiste nell'asportare i bordi di maggior peso e verificare che si possa ottenere un'approssimazione 2 nel grafo sfoltito.

Questo algoritmo è dovuto a Hochbaum e Shmoys.

Difficoltà di approssimazione

Il problema è NP-difficile da affrontare per un rapporto inferiore a 2. Questo risultato è dovuto a Hsu e Nemhauser. La dimostrazione fornita di seguito è una riduzione al problema dell'insieme dominante .

Sia un'istanza (G, k) per il problema dell'insieme dominante. Lo trasformiamo in un'istanza G ' , il grafo completo avente gli stessi vertici, con i seguenti pesi sui bordi: 1 per i bordi di G e 2 per gli altri. Se l'insieme dominante è di dimensione inferiore a k allora G ' ha una soluzione k-centro di costo 1, altrimenti una soluzione di costo 2. Quindi un algoritmo di approssimazione di rapporto inferiore a 2, fornisce una risposta per il problema dell'insieme dominante che è esso stesso NP-difficile .

Casi speciali

Se il grafico è planare esiste uno schema di approssimazione temporale polinomiale per il problema.

Varianti, problemi correlati e applicazioni

Un caso speciale è quando la metrica è euclidea , a volte chiamata k-centro geometrico .

Un modo classico per modificare il problema è aggiungere capacità diverse ai centri. Quindi un certo nodo, se viene scelto come centro, può servire solo un numero limitato di vicini.

Il problema k-median , utilizza lo stesso framework, ma con un'altra funzione da minimizzare. Nel problema ubicazione degli impianti ( impianto posizione problema ), si sostituisce il parametro k dai costi di apertura e collegamento.

Il calcolo di un k -centre può rendere possibile la partizione dei dati . Le distanze rappresentano quindi somiglianze, come per i k-mean .

Note e riferimenti

La traduzione francese proviene dalla traduzione da Nicolas Shabanel di (en) Vijay Vazirani , algoritmi di approssimazione , Springer Verlag , 2001 (poi 2003), 380 p. ( ISBN 978-3-540-65367-7 ), vedere " Algoritmi di approssimazione: sommario " , sul sito web di Nicolas Schabanel .
Samir Khuller e Yoram J. Sussmann, " The Capacitated \ emph {K} -Center Problem ", SIAM J. Discrete Math. , vol. 13, n o 3, 2000, p. 403-418
Dorit S Hochbaum, "Varie nozioni di approssimazioni: buono, migliore, migliore e altro" , in Algoritmi di approssimazione per problemi NP-hard , PWS Publishing Co., 1996, p. 346-446
(in) Michael Garey e David S. Johnson , Computers and Intractability: A Guide to the Theory of NP-completeeness , WH Freeman,1979( ISBN 0-7167-1045-5 ).
(it) Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski e Gerhard Woeginger, “ Metric k-center ” , il Compendio di problemi di ottimizzazione NP ,2000.
Teofilo F. Gonzalez , “ Clustering per ridurre al minimo la massima InterCluster distanza ”, Theoretical Computer Science , vol. 38, 1985, p. 293-306 ( DOI 10.1016 / 0304-3975 (85) 90224-5 )
(it) Sanjoy Dasgupta, “ Lezione 1: Clustering in spazi metrici ” , su Università della California a San Diego ,2013
Jack Edmonds e Delbert Ray Fulkerson , " Bottleneck extrema " , Journal of Combinatorial Theory , vol. 8, n o 3, 1970, p. 299-306.
(it) Vijay Vazirani , algoritmi di approssimazione , Springer Verlag , 2001 (poi 2003), 380 p. ( ISBN 978-3-540-65367-7 ) , cap. 5 ("k-center")
Vedi diapositive 14-19 di Thomas Rothvoss, " Approximation Algorithm " ,2009.
Dorit S. Hochbaum e David B. Shmoys , " A Best Possible Euristic for the k-Center Problem ", Mathematics of Operations Research , vol. 10, n o 2 1985, p. 180-184
Wen-Lian Hsu e George L. Nemhauser, " Problemi di localizzazione dei colli di bottiglia facili e difficili ", Matematica applicata discreta , Elsevier, vol. 1, n o 3, 1979, p. 209-215
David Eisenstat, Philip N. Klein e Claire Mathieu, "Approximating k -center in planar graphs" , in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, 5 gennaio 7, 2014 , 2014, p. 617-627
David P. Williamson e David B. Shmoys, cap. 2.2 "Il problema k-center" , in The Design of Approximation Algorithms , Cambridge University Press

link esterno

(en) Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski e Gerhard Woeginger , " Metric k-center " , su A compendium of NP optimization problems ,2000.
(it) Sanjoy Dasgupta, " Lecture 1: Clustering in metric spaces " , presso l' Università della California a San Diego ,2013