Vi ger den första effektiva (1 − ε) - approximation algoritm för följande problem: Med tanke på en axel-parallell d-dimensionell låda R i R d som innehåller n punkter, beräkna en maximal volym tom axel-parallell d-dimensionell låda som finns i R. Den minsta av denna mängd över alla sådana punktuppsättningar är av ordningen ( 1 n ). Vår algoritm finner en tom axeljusterad låda vars volym är minst (1 − ε) av den maximala i O((8edε −2 ) d · n log d n) tiden. Inga tidigare effektiva exakta eller approximativa algoritmer var kända för detta problem för d ≥ 4. Eftersom problemet nyligen har visat sig vara NP-hård i godtyckligt höga dimensioner (dvs. när d är en del av inmatningen), är förekomsten av en effektiv exakt algoritm osannolik. Vi presenterar också en (1 − ε) - approximation algoritm som, med tanke på en axel-parallell d-dimensionell kub R i R d som innehåller n punkter, beräknar en maximal volym tom axel-parallell hyperkub som ingår i R. Minsta av denna mängd över alla sådana punktuppsättningar visas också vara av ordningen ( 1 n ). En snabbare (1 – ε) approximationsalgoritm, med ett mildare beroende av d i körtiden, erhålls i detta fall.
I REF Dumitrescu m.fl. presenterade den första effektiva 1 − approximation algoritm för problemet med att hitta storleken på den största MEHR.
On the Largest Empty Axis-Parallel Box Amidst n Points
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Computer Science', 'Mathematics']}