Med tanke på en uppsättning F av n positiva funktioner över en markuppsättning X, anser vi problemet med dator x * som minimerar uttrycket f  på F f (x), över x X. En typisk applikation är formpassning, där vi vill approximera en uppsättning P av n element (säg, punkter) genom en form x från en (eventuellt oändliga) familj X av former. Här motsvarar varje punkt p P en funktion f sådan att f (x) är avståndet från p till x, och vi söker en form x som minimerar summan av avstånd från varje punkt i P. I k-klusterande variant, är varje x X en tuple av k former, och f (x) är avståndet från p till dess närmaste form i x. Vårt huvudsakliga resultat är en enhetlig ram för att bygga kärnuppsättningar och approximativa kluster för sådana allmänna uppsättningar av funktioner. För att uppnå våra resultat skapar vi en länk mellan det klassiska och väl definierade begreppet ε-tillnärmningar från teorin om PAC Learning och VC-dimensionen, till det relativt nya (och inte så konsekventa) paradigmet av coresets, som är någon form av "komprimerad representation" av indatauppsättningen F. Med hjälp av traditionella tekniker, innebär en coreset vanligtvis en LTAS (linjär tids approximation) för motsvarande optimeringsproblem, som kan beräknas parallellt, via ett pass över data, och använder endast polylogaritmiskt utrymme (dvs. i den strömmande modellen). För flera funktionsfamiljer F för vilka kärnor är kända för att inte existera, eller motsvarande (ungefärliga) optimeringsproblem är svåra, ger vårt ramverk approximationer av bicriteria, eller kärnor som är stora, men som finns i ett lågdimensionellt utrymme. Vi demonstrerar vårt enhetliga ramverk genom att tillämpa det på projektiva klusterproblem. Vi får nya coreset konstruktioner och betydligt mindre kärnor, över de som dök upp i litteraturen under de senaste åren, för problem som: • k-Median [Har-Peled och Mazumdar,STOC'04], [Chen, SODA'06], [Langberg och Schulman, SODA'10], • k-Line median [Feldman, Fiat och Sharir, FOCS'06], [Deshpande och Varadarajan, STOC'07],
I REF visar författaren en enhetlig ram för att bygga kärnuppsättningar och ungefärlig klusterbildning för sådana allmänna uppsättningar funktioner.
A unified framework for approximating and clustering data
{'venue': "STOC '11", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}