Approximation algorithms for min vector subset-sum over GF(2) In this question vzn asked about the following problem, which I'll call Vector-Subset-Sum.


  Given a set of vectors $v_i$ over GF(2) and a target vector $y$, is there a subset of the $v_i$ summing to $y$?


In the answers, comments, and referenced papers I noted


The decision problem is in P.
The natural minimization problem (finding the smallest subset) is NP-hard.
It's related to the problem of finding sparse codewords in a linear code.


My question is: are there any known polynomial-time approximation algorithms for the minimization problem in (2)? I know very little about coding theory, so there may be some obvious or well-known approximation-preserving reductions to (3) that I have not seen.
Dumer, Miccancio and Sudan showed that the minimum distance of a linear code is not approximable to any constant factor in randomized polynomial time, unless $\mathsf{NP} = \mathsf{RP}$. The minimum distance problem is the same as your problem if the $v_i$'s form the columns of the parity check matrix and $y = 0$.