Abstrakt. Med tanke på n efterfrågepunkter i planet, p-centrum problemet är att hitta p tillförselpunkter (var som helst i planet) för att minimera det maximala avståndet från en demo och punkt till sin respektive närmaste leveranspunkt. Problemet med p-median är att minimera summan av avstånden från efterfrågepunkter till deras respektive närmaste försörjningspunkter. Vi bevisar att p-center och p-media problem i förhållande till både Euclidean och rektilinjära mätvärden är NP-hård. Faktum är att vi bevisar att det är NP-hårdt att tillnärma p-centerproblemen tillräckligt noga. Minskningarna beror på 3-tillfredställbarhet.
Precis som K-means problemet, K-median problemet är NP-hård, även för D = 2 REF.
ON THE COMPLEXITY OF SOME COMMON GEOMETRIC LOCATION PROBLEMS
{'venue': 'SIAM J. COMPUTING', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}