On largest volume simplices and sub-determinants

Abstract: We show that the problem of finding the simplex of largest volume in the convex hull of

n

points in

m a t h b b Q^{d}

can be approximated with a factor of

O (l o g d)^{d / 2}

in polynomial time. This improves upon the previously best known approximation guarantee of

d^{(d - 1) / 2}

by Khachiyan. On the other hand, we show that there exists a constant

c > 1

such that this problem cannot be approximated with a factor of

c^{d}

, unless

P = N P

. % This improves over the

1.09

inapproximability that was previously known. Our hardness result holds even if

n = O (d)

, in which case there exists a

-approximation algorithm that relies on recent sampling techniques, where

is again a constant. We show that similar results hold for the problem of finding the largest absolute value of a subdeterminant of a

d i m e s n

matrix.

Recommendations

Cited in

(27)

This page was built for publication: On largest volume simplices and sub-determinants