Sammanfattning I detta dokument anser vi att en klass av begränsade kluster problem av punkter i R d, där d kan vara ganska hög. Ett gemensamt drag i dessa problem är att deras optimala kluster inte längre har lokaliteten (på grund av ytterligare begränsningar), som är en viktig egenskap som krävs av många algoritmer för sina oinskränkta motsvarigheter. För att övervinna svårigheten som orsakas av förlusten av lokalitet, presenterar vi i detta dokument en enhetlig ram, kallad Peeling-and-Enclosing (PnE), för att iterativt lösa två varianter av de begränsade klusterproblem, begränsade k-means kluster (k-CMeans) och begränsade k-median kluster (k-CMedian). Vårt ramverk generaliserar Kumar et al.'s eleganta k-means clustring approach [51] från okonstruerade data till begränsade data, och är baserad på två fristående geometriska tekniker, kallade Simplex Lemma och Weaker Simplex Lemma, för k-CMeans respektive kCMedianus. Den simplex lemma (eller svagare simplex lemma) gör det möjligt för oss att effektivt approxima medelvärdet (eller median) punkt av en okänd uppsättning punkter genom att söka en liten storlek rutnät, oberoende av dimensionaliteten i utrymmet, i en simplex (eller den omgivande regionen av en simplex), och därmed kan Detta arbete stöds delvis av NSF genom bidrag IIS-1115220, IIS-1422591, CCF-1422324, CNS-1547167, CCF-1656905, och CCF-1716400. Den första författaren fick också stöd av en startfond från Michigan State University. En preliminär version av denna uppsats har dykt upp i tjugosjätte årliga ACM-SIAM Symposium på Discrete Algoritmer (SODA 2015) 1 är fasta tal, vårt ramverk genererar, i nästan linjär tid (dvs., O(n(log n) k+1 d)), O(log n) k ) k-tuple kandidater för k medelvärde eller medianpoäng, och en av dem framkallar en (1 + )-uppskattning för k-CMeans eller k-CMedian, där n är antalet poäng. Genom att kombinera detta enhetliga ramverk med en problemspecifik urvalsalgoritm (som bestämmer den bästa k-tuple-kandidaten) får vi en (1 + )-uppskattning för var och en av de begränsade klusterproblemen. Vår ram förbättrar avsevärt de mest kända resultaten för dessa problem. Vi förväntar oss att vår teknik kommer att tillämpas på andra begränsade klusterproblem utan ort.
Mycket nyligen gav REF en (1 + ) - approximation för feltolerant k-median problem när k = O(1) och det underliggande metriska utrymmet är Euclidean.
A Unified Framework for Clustering Constrained Data without Locality Property
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}