This is more of an extended comment than an answer, but I hope it might help clarify the problem. The OP seems to have two things in mind: 1) there are inherent errors (the $E$) in the measurements of distance and/or location, and 2) there is an unknown constant $k$ affecting all measurements of distance from the observation points $P_i$ to the object of interest $O$. I was puzzled by what this second concern meant until I came up with a possible, albeit fanciful, interpretation. It may not be at all what the OP means, in which case I hope he or she (or someone) will clarify the actual intent, but I think it at least produces a reasonably nice problem in its own right.
Suppose you know the exact locations of your observation points, meaning in particular that you know the exact distance between any pair of them. Let's say you've measured these distances in kilometers. (At some point one might generalize the problem to incorporate errors in these measurements as well, but let's leave well enough alone for now.) You now want to know the location of $O$, so you dispatch surveyors from each of the observation points to measure the distances from $O$ to each $P_i$. If each surveyor were able to report the exact distance in kilometers, you'd really only need to hear from two of them in order to discern the exact location of $O$ (assuming you know which side of the line segment connecting the two observation points $O$ lies on -- if you don't know even that much, then you need three observations points, and they can't lie in row).
If the surveyors report approximate distances in kilometers, together with an estimate of the error, say $d_i\pm e_i$ (perhaps with the errors reported in meters, or even centimeters), it seems straightforward, conceptually, to draw the $n$ annuli centered at the observation points, determine if they have a non-empty intersection, enclose it in a circle of minimal radius, and use the center of that circle for the estimated location of $O$ and its radius for the uncertainty. Precisely how (or whether) one can do that efficiently, I'll leave for the experts in computational geometry.
But now -- and here's where I think it gets interesting -- suppose your surveyors, who learned their skills in a foreign land, come back and say something like "The distance from $O$ to $P_i$ is $y_i$ dythrms, give or take $x_i$ frklfts." And then they vanish.
You turn to your advisor from the Bureau of Standards and say, "What the heck?" She replies, "I'm told that a dythrm is the distance around the Holy Sepulchre in the kingdom where the surveyors went to school, and a frklft is the length of the Royal Sceptre. I think we can assume one is comparable to a kilometer and the other to a meter. But I'm afraid that's all I know."
The question is, based on numbers that are reported in units you're not familiar with, can you nonetheless get an estimate on the location of $O$ and, as a consequence, estimate the conversion factor(s) between the surveyors' units and your own (in particular the unknown factor $k$ that tells you how many kilometers there are in a dythrm)?
It's pretty clear you need to know something about the relative size of dythrms and frklfts. Otherwise you'd be left saying "For all we know a dythrm is an inch and a frklft is a parsec, and we just paid those damn surveyors a million gazebos for nothing!" It might make sense to assume that the ratio of dythrms to frklfts is known (i.e., in effect assume the surveyors report all numbers using just dythrms). But it might be more fun to see if you can figure out the smallest ratio of frklfts to dythrms that is consistent with the reported numbers $y_i$ and $x_i$ (i.e, ask how small can a frklft be as a fraction of a dythrm and still have all the measurements make sense).
One case that's relatively easy to solve is if all the measurements are exact, so there are no frklfts to worry about. In that case you only need the distances to three observation points. If the (unknown) distance in kilometers from $P_i$ to $O$ is $ky_i$ for $i=1,2,3$, and if the distances $P_1P_2$, $P_2P_3$, and $P_1P_3$ are $a$, $b$, and $c$ (also in kilometers), then the law of cosines says
$$a^2 = (ky_1)^2 + (ky_2)^2 - 2(ky_1)(ky_2)\cos\alpha,$$
$$b^2 = (ky_2)^2 + (ky_3)^2 - 2(ky_2)(ky_3)\cos\beta,$$
and
$$c^2 = (ky_1)^2 + (ky_3)^2 - 2(ky_1)(ky_3)\cos(\alpha+\beta),$$
where $\alpha$ and $\beta$ are the angles $\angle P_1OP_2$ and $\angle P_2OP_3$, respectively (referring to the figure in the original problem). The first two equations can be solved for $\cos\alpha$ and $\cos\beta$ in terms of $k$, and these can be substituted into the third equation after rewriting $\cos(\alpha+\beta)$ as $\cos\alpha\cos\beta-\sqrt{(1-\cos^2\alpha)(1-\cos^2\beta)}$. The result is a rather messy looking equation (I think it's a quartic in $k^2$ with coefficients in the six distances), but whatever it is, it can certainly be solved for $k$ (and if it can't, that tells you the measurements violate a triangle inequality of some sort).
My apologies for writing an overly long comment, particularly if it has nothing to do with what the OP is really asking. Mostly I was just perplexed by the meaning of an unknown scaling factor.
