Bypassing UGC from some Optimal Geometric Inapproximability Results
Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu · 2010
The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance seems critical in these proofs. In this work we bypass the UGC assumption in inapproximabil-ity results for two geometric problems, obtaining a tight NP-hardness result in each case. The first problem known as theLp SubspaceApproximation is a generalization of the classic least squares regression problem. Here, the input consists of a set of points S = {a1,..., am} ⊆ R n and a parameter k (possibly depending on n). The goal is to find a subspace H of Rn of dimension k that minimizes the sum of the pth powers of the distances to the points. For p = 2, k = n − 1, this reduces to the least squares regression problem, while for p =∞, k = 0 it reduces to the problem of finding a ball of minimum radius enclosing all the points. We show that for any fixed p (2 0. This matches the γp approximation algorithm obtained by Deshpande,