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.