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.
För att hitta den huvudsakliga k × k submatrisen av en positiv semidefinitmatris med den största bestämningsfaktorn, gav REF en algoritm som får en approximation av e −(k+o(k)).
Randomized Rounding for the Largest Simplex Problem
{'venue': "STOC '15", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}