K-center problemet är en kanonisk och långstuderad anläggning plats och kluster problem med många tillämpningar i både symmetriska och asymmetriska former. Båda versionerna av problemet har snäva approximationsfaktorer för värsta fall: en 2-approximation för symmetrisk k-center och en O(log * (k)-approximation för den asymmetriska versionen. För att förbättra dessa kvoter måste man därför gå längre än i värsta fall. I detta arbete tar vi denna strategi och ger starka positiva resultat både för de asymmetriska och symmetriska k-centerproblemen under en mycket naturlig ingångsstabilitet (förutsatt) tillstånd som kallas α-perturbation resilience [11], där det anges att den optimala lösningen inte förändras under någon α-faktor perturbation till ingångsavstånden. Vi visar att genom att anta 2-perturbation motståndskraft, den exakta lösningen för den asymmetriska k-center problem kan hittas i polynom tid. Enligt vår kunskap är detta det första problemet som är svårt att approximera till någon konstant faktor i värsta fall, men ändå kan lösas optimalt i polynom tid under perturbation resilience för ett konstant värde av α. Dessutom visar vi att vårt resultat är tight genom att visa symmetrisk k-center under (2 − )-perturbation motståndskraft är svårt om inte N P = RP. Detta är det första tighta resultatet för alla problem under perturbation motståndskraft, dvs. detta är första gången det exakta värdet av α för vilken problemet växlar från att vara NP-hård till effektivt beräkningsbar har hittats. Våra resultat illustrerar ett överraskande samband mellan symmetriska och asymmetriska k-centerfall under perturbationsresiliens. Till skillnad från approximationsförhållandet, för vilket symmetrisk k-center lätt kan lösas till en faktor av 2 men asymmetrisk k-center inte kan approximeras till någon konstant faktor, kan både symmetrisk och asymmetrisk k-center lösas optimalt under resiliens till 2-perturbationer.
Balcan m.fl. REF konstruerade algoritmer för k-center och asymmetrisk k-center under 2-perturberingsresiliens och (3, )-perturberingsresiliens, och de visade ingen polynom-tidsalgoritm kan lösa k-center under (2 - )-uppskattning stabilitet (ett begrepp som är starkare än perturbationsresiliens) om inte N P = RP.
$k$-center Clustering under Perturbation Resilience
{'venue': 'ICALP 2016', 'journal': 'arXiv: Data Structures and Algorithms', 'mag_field_of_study': ['Computer Science', 'Mathematics']}