MAXIMUM D-VECTOR COVERING

• INSTANCE: Set X of vectors in $[0,1]^{d}$.

• SOLUTION: A partition of X into m subsets $S_1, \ldots, S_m$.

• MEASURE: The number of unit covers in $\{S_{1},\ldots,S_{m}\}$ where a set S of vectors in $[0,1]^{d}$ is a unit cover if, for any $i\leq d$, the sum of the i-th components of the elements in S is at least 1.

  
  

• Good News: Approximable within 4/3 for d=1 [42] and within $(2 \ln d)/(1+o(()1))$ for $d\geq 2$ [11].