How to determine approximability of a problem when we don't know how good a solution is?
Definition of a well-formed optimization problem

It seems to me the core problem you have here is that the problem you have defined is not what I'd call a well-formed optimization problem.  Normally, an optimization problem looks something like this:

Input: $x$
Goal: find $y$ that maximizes $\Phi(x,y)$

where $\Phi$ is some objective function that's specified as part of the problem statement.  The key point here is that the objective function has to be computable, as a function of the input and the proposed output.

Your proposed formalization of the WSN localization problem does not have this form: the objective function is not computable as a function of the information known to us.  Therefore, it is not a well-formed optimization problem.

This explains the problem you're having.  The reason you can't compare how good different solutions are is that you don't have a computable way to measure how good a single solution is, given the information available to you.  Consequently, your problem does not fit into the standard framework of optimization problems and approximation algorithms.  This means you can't take advantage of all that theory, and strange things can happen.

So, at this point you have two options.  First, you can try to formulate your problem as a way that does qualify in this framework, i.e., where you do have a computable objective function.  The other option is to accept that you don't fit into this framework and you'll have to develop everything from scratch without being able to use the existing framework as is.

Another way to put this: if your objective function depends on values that aren't known (aren't part of the input), then what you haven't is not purely an algorithmic problem.  To make this an algorithmic task, you need a way to measure success.  One candidate way to do this would be to establish some probability distribution on the locations of the sensors, then frame this as a statistical inference problem, where you want to find the maximum likelihood estimate, or something like that.

Another approach would be to choose a different objective function, that is computable.  For instance, maybe you could evaluate the accuracy of a solution in terms of how closely it matches the givens: for what fraction of edges $\{v,v'\}$ do we have $||v_\text{est}-v'_\text{est}|| &lt; R+\varepsilon$, and what fraction of non-edges $v,v'$ do we have $||v_\text{est}-v'_\text{est}|| &gt; R-\varepsilon$; maybe the objective function is the sum of these two fractions, or something.  Of course, this is a different objective function, so it's maximizing something different, and the solution to that optimization problem might or might not match what you're actually looking for.



For posterity, here's some feedback on an older version of the problem, which has now been addressed by the revised question.

I see some misconceptions in this question, both about how we measure the quality of approximations, and about when approximation algorithms are applicable.  The best answer I can give is to clear up these confusions/misconceptions; that will help you think about this kind of problem more clearly.

Definition of the approximation ratio

You have a confusion about how we normally measure the quality of an approximation, in the standard theory of approximation algorithms.  This shows up in your discussion of approximation algorithms for subset sum.

With subset-sum, the objective function we are maximizing is $\text{sum}(B)$.  In the standard theory of approximability, we measure the quality of an approximation by how good the value of $\text{sum}(B)$ is, compared to the optimal value of that for the optimal choice of $B$ -- not compared to $t$.

When we ask whether there is a $2$-approximation for subset-sum, we ask whether there's an algorithm that outputs a set $B_\text{approx}$ such that

$${\text{sum}(B_\text{approx}) \over \text{sum}(B_\text{opt})} \ge 1/2,$$

where $B_\text{opt}$ is the optimal solution (the one that maximizes $\text{sum}(B)$).  The ratio on the left-hand-side is called the approximation ratio.  Notice how $t$ doesn't appear in this quantity.  The approximation ratio is defined with reference to the optimal solution, not with reference to $t$. 

When approximation algorithms are applicable

Approximation algorithms are only applicable to optimization problems.

The "WSN localization problem", as you have defined it, is not an optimization problem: it is a decision problem.    Since it's not an optimization problem, the entire concept of an approximation algorithm doesn't enter into it.

Asking "is it approximable?" is a category error: it's like asking "Is 'flying' a mammal?" -- 'flying' isn't even a noun, let alone an animal.

You then talk about two metrics.  If you pick one of those metrics, you could define an optimization problem that is based upon the "WSN localization problem", where you ask to find the placement of node positions that complies with all the constraints and that maximizes (or minimizes) that metrics.  Then you would have an optimization problem.

However, when you have two metrics, we don't get a well-defined optimization problem, since it's not clear what would count as optimal.  Indeed, there might be multiple solutions that each achieve a different tradeoff between these two metrics, and is "Pareto-optimal".  (See also What is a bicriteria approximation algorithm?.)

So, to count as an optimization function, you have to be maximizing/minimizing a single objective function; the standard theory of approximation algorithms is only applicable when you have a problem that is of this form.  If your problem isn't of this form, it probably doesn't make sense to ask if it is approximable, as standard definitions of approximability don't apply.