1
$\begingroup$

given a set of n points P and a nxn matrix M such that for every two point u,v where M[u,v] is the distance between u and v , and the distance is pseudo metric, is there a property testing algorithem such that given a number D >0 and ε in the range (0, 1) returns the following:

  • if the diameter of P is D or less, the algorithem returns "yes" with probability at least 2/3
  • if the diameter of P is more than 2D and we cannot make the diameter of P to become 2D or less by removing εn points in P , the algorithem returns "no" with probability at least 2/3.
  • in every other situiation , it doesnt matter what the algorithem answers.

i am aware that there is a deterministic algorithem for approximating the diameter by a factor of 2 (The classic 2-approximation algorithm for this problem) that uses running time O(nd), and which is to choose an arbitrary point and then return the maximum distance to another point. The diameter is no smaller than this value and no larger than twice this value.but i cant see a conncection to the given problem .

$\endgroup$

1 Answer 1

0
$\begingroup$

This problem indeed seems very suitable for property testing:

Claim: If the diameter of P is more than 2D and we cannot make the diameter of P 2D or less by removing εn points in P, then we can find $O(\varepsilon (1-\varepsilon) n^2)$ pairs of points at distance $\geq D$.

Proof: Take two points so that their distance is at least $2D$. Every point $p$, is at distance $\geq D$ of one of the two points, by triangular inequality. We therefore obtain $n$ pairs of points, containing one of those two, at distance $\geq D$ of each other. Then remove the two points and repeat the process, until the diameter is $\leq 2D$. This takes at least $\epsilon n /2$ iterations, by the assumption in the statement of the claim. Hence in total we obtain at least $n + n-2 + ... + n-(2\lfloor \varepsilon n/2 \rfloor)$ pairs of points at distance $\geq D$, that is, $O(\varepsilon (1-\varepsilon) n^2)$. Note that this bound is tight, we can reach it by having two far away packs of close points, one of $\varepsilon n$ points and the other with $(1-\varepsilon) n$ points.

Now the algorithm: You can sample $\frac{1}{\varepsilon(1-\varepsilon)}$ pairs of points at random: if one of these pairs $(p_1, p_2)$ is such that the distance between $p_1$ and $p_2$ is more than $D$ then answer no, otherwise answer yes.

  • If the diameter is $D$ or less then no such pair of points exists, hence the algorithm answers "yes" with probability 1.
  • If the diameter is more than $2D$, and not reducible under $2D$ by removing $\varepsilon n$ points then by the previous claim each sampled pair of points has probability $O(\varepsilon(1-\varepsilon))$ to be at distance $\geq D$ of each other. As we sample $O(\frac{1}{\varepsilon(1-\varepsilon)})$ pairs we have a constant probability of answering no.

Repeating this algorithm a suitable constant number of times reduces the probability of failure in the second case below $1/3$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.