Den maximala volymen j-simplex problem ber att beräkna j-dimensionell simplex av maximal volym inuti konvex skrov av en given uppsättning n punkter i Q d. Vi ger en deterministisk approximation algoritm för detta problem som uppnår en approximation förhållande e j/2+o(j). Problemet är känt för att vara NP-hård till ungefärlig inom en faktor av c j för vissa konstant c > 1. Vår algoritm ger också en faktor e j+o(j) approximation för problemet att hitta huvud j × j submatris av en rank d positiv semidefinit matris med den största determinanten. Vi uppnår vår approximation genom avrundning lösningar till en generalisering av D-optimala design problem, eller, motsvarande, den dubbla av en lämplig minsta inneslutning ellipsoid problem. Våra argument ger ett kort och enkelt bevis på en begränsad invertibilitetsprincip för bestämningsfaktorer.
I REF studerades också ett annat relaterat problem med att hitta en k-dimensionell simplex med maximal volym inuti ett visst konvext skrov, som kan reduceras till det tidigare problemet under kardinalitetsbegränsning.
Randomized Rounding for the Largest Simplex Problem
{'venue': "STOC '15", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}