Vi visar att problemet med att hitta den simplex av största volymen i konvexa skrov av n punkter i Q d kan approximeras med en faktor av O(log d) d/2 i polynom tid. Detta förbättrar den tidigare mest kända approximationsgarantin för d (d-1)/2 av Khachiyan. Å andra sidan visar vi att det finns en konstant c > 1 sådan att detta problem inte kan approximeras med en faktor c d, om inte P = N P. Vårt hårdhetsresultat håller även om n = O(d), i vilket fall det finns ac d - approximation algoritm som bygger på senaste provtagningstekniker, varc är återigen en konstant. Vi visar att liknande resultat håller för problemet med att hitta det största absoluta värdet av en subdeterminant av en d × n matris.
Deras resultat innebär en e- approximationsgrad för ekv. (1.1) I specialfallet k = p. Å andra sidan, Summa et al. REF visade att det finns en konstant c > 1 så att polynom-tid c-tillnärmning av D-optimalitet är omöjligt för p = k-fallet, om inte P = NP.
On largest volume simplices and sub-determinants
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}