Vi anser att problemet med att beräkna den yttre-radii av punktuppsättningar. I detta problem, vi ges heltal n, d, k där k ≤ d, och en uppsättning P av n punkter i R d. Målet är att beräkna den yttre k-radius av P, betecknad av R k (P ), vilket är det minsta, över allt är Euclidean avståndet mellan punkten p och platt F. Computing radier av punktuppsättningar är ett grundläggande problem i beräknings konvexitet med många betydande tillämpningar. Problemet medger en polynom tid algoritm när dimensionen d är konstant [16]. Här är vi intresserade av det allmänna fallet när dimensionen d inte är fast och kan vara så stor som n, där problemet blir NP-hård även för k = 1. Det är känt att R k (P ) kan approximeras i polynom tid med en faktor (1 + ε), för alla ε > 0, när d − k är en fast konstant [8, 23]. A * Forskning av den första författaren stöds av NSF CAREER Award CCR-0237431. Forskning av den andra författaren stöds av en NSERC upptäckt bidrag. Forskning av den tredje och fjärde författarna stöds av NSF bidrag DMI-0231600. En preliminär version av denna artikel publicerades som : (i) K. R. Varadarajan, S. Venkatesh, och J. Zhang, Caiming radier av punktuppsättningar i höga dimensioner, Proc. 43:e IEEE Symp. Hittad. Räkna. Sci., 2002, och (ii) 1 polynom tid algoritm som garanterar en faktor för O ( ε log n) approximation för R 1 (P ), bredden på punkten som P, är underförstått av resultaten av Nemirovski et al. [29] och Nesterov [28]. I detta papper visar vi att R k (P ) kan approximeras med ett förhållande av O( ε log n) för alla 1 ≤ k ≤ d, vilket motsvarar den tidigare mest kända kvoten för approximering av specialfallet R 1 (P ), bredden på punktuppsättningen P. Vår algoritm är baserad på semidefinit programmeringsavkoppling med en ny blandad deterministisk och randomiserad avrundning förfarande. Vi visar också ett oåtkomligt resultat som ger bevis för att vår approximationsalgoritm går bra för ett stort spektrum av k. Vi visar att det finns en konstant δ > 0 så att följande håller för alla 0 < ε < 1: det finns ingen polynomalgoritm som approximerar R k (P ) inom (log n) Vårt omätbarhetsresultat för R k (P ) förlänger ett tidigare känt hårdhetsresultat av Brieden [15], och bevisas genom att modifiera Briedens konstruktion med hjälp av grundläggande idéer från PCP teori.
I själva verket finns det en konstant δ > 0 sådan att det är Quasi-NP-hård, dvs, innebär NP  en DTIME(2 (log n) O(1) ), att även hitta en (log n) δ approximation till den bästa monteringen k-subrymd när k ≥ d för någon fast > 0 REF.
On Approximating the Radii of Point Sets in High Dimensions
{'venue': 'FOCS', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}